@inproceedings{3940d76cc6d041d8940150b95fdc1c1d,

title = "Fast Witness Extraction using a Decision Oracle",

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.",

author = "Andreas Bj{\"o}rklund and Petteri Kaski and Lukasz Kowalik",

year = "2014",

doi = "10.1007/978-3-662-44777-2_13",

language = "English",

isbn = "978-3-662-44777-2",

volume = "8737",

publisher = "Springer",

pages = "149--160",

editor = "Andreas Schulz and Dorothea Wagner",

booktitle = "Algorithms - ESA 2014/Lecture notes in computer science",

address = "Germany",

note = "European Symposium on Algorithms ; Conference date: 08-09-2014 Through 10-09-2014",

}