Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Fast Witness Extraction using a Decision Oracle

Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz (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:
author
; and
organization
publishing date
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
0302-9743
1611-3349
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
2021-09-29 04:36:32
@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         = {0302-9743},
  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},
}