Fast Witness Extraction using a Decision Oracle

Summary, in English

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örklund; Petteri Kaski; Lukasz Kowalik
• Editor: Andreas Schulz; Dorothea Wagner
• Department/s: Department of Computer Science; Parallel Systems
• Publishing year: 2014
• Language: English
• Pages: 149-160
• Publication/Series: Algorithms - ESA 2014/Lecture notes in computer science
• Volume: 8737
• Links: http://dx.doi.org/10.1007/978-3-662-44777-2_13
• Document type: Conference paper
• Publisher: Springer
• Topic: Computer Science
• Conference name: European Symposium on Algorithms
• Conference date: 2014-09-08 - 2014-09-10
• Conference place: Wroclaw, Poland
• Status: Published
• Project: Exact algorithms
• Research group: Algorithms
• ISBN/ISSN/Other: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-662-44777-2