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.

Back to the research colloquium site.