In 2011, Fomin and Villanger presented a surprising parameterized algorithm for the Minimum Fill-in problem (add at most k edges to a graph in order to make it chordal) that works in subexponential parameterized time; more precisely in time 2^{O(sqrt{k} log k)} * poly(n). Following their approach, several algorithms with similar running times were designed for related graph modification problems. In all these cases, the tackled problem is completion to some subclass Pi of chordal graphs, i.e., to add as few edges as possible in order to make the given graph belong to Pi. Numerous examples show that diverging from this template even slightly makes it possible to refute the existence of such an efficient parameterized algorithms under ETH; this makes the considered completion problems curious singularity points on the complexity landscape. Also, it is currently unknown whether finding even  faster algorithms, e.g. with running time 2^{o(sqrt{k})} * poly(n), is possible for Minimum Fill-in and related problems.

 

In this talk we will briefly survey the known algorithmic results on subexponential parameterized algorithms for completion problems to subclasses of chordal graphs. Then we will sketch a new work that attempts to answer the question of finding even faster algorithms for these problems by (a) augmenting the classic reductions from ETH by tools related to the PCP theorem and (b) basing the lower bounds on a certain conjecture regarding inapproximability of the Minimum Bisection problem.

 

The talk will be based on a joint work with Ivan Bliznets, Marek Cygan, Pawel Komosa, and Lukas Mach.