License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.22
URN: urn:nbn:de:0030-drops-69218
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6921/
Go to the corresponding LIPIcs Volume Portal

Meeks, Kitty

Randomised Enumeration of Small Witnesses Using a Decision Oracle

pdf-format:
LIPIcs-IPEC-2016-22.pdf (0.5 MB)

Abstract

Many combinatorial problems involve determining whether a universe of n elements contains a witness consisting of k elements which have some specified property. In this paper we investigate the relationship between the decision and enumeration versions of such problems: efficient methods are known for transforming a decision algorithm into a search procedure that finds a single witness, but even finding a second witness is not so straightforward in general. In this paper we show that, if the decision version of the problem belongs to FPT, there is a randomised algorithm which enumerates all witnesses in time f(k)*poly(n)*N, where N is the total number of witnesses and f is a computable function. This also gives rise to an efficient algorithm to count the total number of witnesses when this number is small.

BibTeX - Entry

@InProceedings{meeks:LIPIcs:2017:6921,
  author =	{Kitty Meeks},
  title =	{{Randomised Enumeration of Small Witnesses Using a Decision Oracle}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{22:1--22:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6921},
  URN =		{urn:nbn:de:0030-drops-69218},
  doi =		{10.4230/LIPIcs.IPEC.2016.22},
  annote =	{Keywords: enumeration algorithms, parameterized complexity, randomized algorithms, color coding}
}

Keywords: enumeration algorithms, parameterized complexity, randomized algorithms, color coding
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI