Smaller Kernels for Minimum Fill-In on Sparse Graphs

The problem is known to be NP-hard, and various approximation and fixed-parameter tractable algorithms are known. We look at the problem of finding small "kernels" for the problem in various classes of sparse graphs, with the solution size k as the parameter. A kernel of a problem instance is an equivalent instance which can be obtained in polynomial time, and whose size is bounded by a function of the parameter k alone.

We obtain linear (O(k)-size) kernels for the problem when restricted to planar graphs, and subquadratic (O(k^{3/2})-size) kernels on H-minor free and d-degenerate graphs for any fixed graph H and number d. This improves the previous best known bound of O(k^2) for these graph classes, and also ensures that the kernel belongs to the same class -- planar, H-minor free, or d-degenerate, respectively -- as the input graph. Note that while the algorithm with the O(k^{2}) bound is the best known for graphs in general, it does not preserve the sparsity of input graphs.

As an application of these new kernels, we show how they imply better approximation algorithms for the problem on planar and H-minor free graphs.

This is joint work with Fedor V. Fomin and Yngve Villanger of the Department of Informatics, University of Bergen, Norway. It has appeared in the proceedings of FSTTCS 2011.