Fast Witness Extraction using a Decision Oracle
(2014) European Symposium on Algorithms 8737. p.149-160- 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.... (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 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. (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
- 2014-09-08 - 2014-09-10
- external identifiers
-
- wos:000345502900013
- scopus:84958552537
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-662-44777-2
- DOI
- 10.1007/978-3-662-44777-2_13
- project
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- 3940d76c-c6d0-41d8-9401-50b95fdc1c1d (old id 4813246)
- date added to LUP
- 2016-04-01 10:50:27
- date last changed
- 2024-04-21 23:00:38
@inproceedings{3940d76c-c6d0-41d8-9401-50b95fdc1c1d,
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 = {{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 = {{978-3-662-44777-2}},
issn = {{1611-3349}},
language = {{eng}},
pages = {{149--160}},
publisher = {{Springer}},
title = {{Fast Witness Extraction using a Decision Oracle}},
url = {{http://dx.doi.org/10.1007/978-3-662-44777-2_13}},
doi = {{10.1007/978-3-662-44777-2_13}},
volume = {{8737}},
year = {{2014}},
}