TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 05.01.2017

isti-logo

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.

 

Date
Speaker
Location
Language
05.01.2017
16:15
Philipp Zschoche
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe