Advanced

Fast Witness Extraction using a Decision Oracle

Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz (2014) European Symposium on Algorithms In Algorithms - ESA 2014/Lecture notes in computer science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms - ESA 2014/Lecture notes in computer science
editor
Schulz, Andreas; Wagner, Dorothea; and
volume
8737
pages
12 pages
publisher
Springer
conference name
European Symposium on Algorithms
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
2014-11-25 14:06:09
date last changed
2017-07-23 03:25:04
@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},
  volume       = {8737},
  year         = {2014},
}