Fast Witness Extraction using a Decision Oracle

Andreas Björklund, Petteri Kaski, Lukasz Kowalik

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

13 Citations (SciVal)

Abstract

The gist of many (NP-)hard combinatorial problems is to decide whether a universe of n elements contains a witness consisting of k elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for large values of n. By relying on techniques from combinatorial group testing, we demonstrate that a witness may be extracted with O(klogn) queries to either a deterministic or a randomized set inclusion oracle with one-sided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebra-based FPT algorithms are practical, in particular in the setting of the k-path problem. Also discussed are engineering issues such as optimizing finite field arithmetic.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2014/Lecture notes in computer science
EditorsAndreas Schulz, Dorothea Wagner
PublisherSpringer
Pages149-160
Number of pages12
Volume8737
ISBN (Print)978-3-662-44777-2
DOIs
Publication statusPublished - 2014
EventEuropean Symposium on Algorithms - Wroclaw, Poland
Duration: 2014 Sep 82014 Sep 10

Publication series

Name
Volume8737
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Symposium on Algorithms
Country/TerritoryPoland
CityWroclaw
Period2014/09/082014/09/10

Subject classification (UKÄ)

  • Computer Science

Fingerprint

Dive into the research topics of 'Fast Witness Extraction using a Decision Oracle'. Together they form a unique fingerprint.

Cite this