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.

• Författare: Andreas Björklund; Petteri Kaski; Lukasz Kowalik
• Redaktör: Andreas Schulz; Dorothea Wagner
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 149-160
• Publikation/Tidskrift/Serie: Algorithms - ESA 2014/Lecture notes in computer science
• Volym: 8737
• Länkar: http://dx.doi.org/10.1007/978-3-662-44777-2_13
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: European Symposium on Algorithms
• Conference date: 2014-09-08 - 2014-09-10
• Conference place: Wroclaw, Poland
• Status: Published
• Projekt: Exact algorithms
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-662-44777-2