Fast Witness Extraction using a Decision Oracle
(2014) European Symposium on Algorithms 8737. p.149160 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 algebrabased FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NOdecision 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 onesided probability of error.... (More)
 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 algebrabased FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NOdecision 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 onesided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebrabased FPT algorithms are practical, in particular in the setting of the kpath problem. Also discussed are engineering issues such as optimizing finite field arithmetic. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4813246
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Kowalik, Lukasz
 organization
 publishing date
 2014
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Algorithms  ESA 2014/Lecture notes in computer science
 editor
 Schulz, Andreas and Wagner, Dorothea
 volume
 8737
 pages
 12 pages
 publisher
 Springer
 conference name
 European Symposium on Algorithms
 conference location
 Wroclaw, Poland
 conference dates
 20140908  20140910
 external identifiers

 wos:000345502900013
 scopus:84958552537
 ISSN
 03029743
 16113349
 ISBN
 9783662447772
 DOI
 10.1007/9783662447772_13
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 3940d76cc6d041d8940150b95fdc1c1d (old id 4813246)
 date added to LUP
 20160401 10:50:27
 date last changed
 20210929 04:36:32
@inproceedings{3940d76cc6d041d8940150b95fdc1c1d, 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 algebrabased FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NOdecision 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 onesided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebrabased FPT algorithms are practical, in particular in the setting of the kpath problem. Also discussed are engineering issues such as optimizing finite field arithmetic.}, author = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}, booktitle = {Algorithms  ESA 2014/Lecture notes in computer science}, editor = {Schulz, Andreas and Wagner, Dorothea}, isbn = {9783662447772}, issn = {03029743}, language = {eng}, pages = {149160}, publisher = {Springer}, title = {Fast Witness Extraction using a Decision Oracle}, url = {http://dx.doi.org/10.1007/9783662447772_13}, doi = {10.1007/9783662447772_13}, volume = {8737}, year = {2014}, }