TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 05.01.2017


Page Content

to Navigation

Randomised enumeration of small witnesses using a decision oracle

Philipp Zschoche (TU Berlin)


Many combinatorial problems involve determining whether a universe of n elements contains a witness consisting of k elements which have some specified property. In a recent paper, Kitty Meeks investigates 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. I present the main result of the paper which states that, if the decision version of the problem belongs to FPT, there is a randomised algorithm which enumerates all witnesses in f(k) · poly(n) · N expected time, 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.


Philipp Zschoche
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe