2026-07-23T19:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6921 2024-03-06T10:38:49Z ddc:004 open_access

Randomised Enumeration of Small Witnesses Using a Decision Oracle Meeks, Kitty enumeration algorithms parameterized complexity randomized algorithms color coding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kitty Meeks 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.22 urn:nbn:de:0030-drops-69218 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode