Minimum fill-in of sparse graphs: kernelization and approximation (Q2258069)

Given a graph \(G=(V,E)\) and a non-negative integer \(k\), the Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most \(k\) edges. The problem was proved to be NP-complete and there are known its approximation and FPT algorithms. The first and the third author of this paper developed an FPT algorithm for the problem which runs in \(O(2^{O(\sqrt k\log k)}+k^2nm)\) time. In this paper the authors develop kernelization algorithms for the problem for several classes of sparse graphs. A kernelization algorithm reduces the input instance down to an instance with size bounded by a polynomial \(p(k)\) in \(k\) while preserving the answer. I.e., if \((G, k)\) is an instance of the Minimum Fill-in problem, the pair \((G^\prime, k^\prime)\) is a linear kernel if \(G^\prime\) is a graph of size \(O(k)\) and there is a fill-in of \(G\) with at most \(k\) edges if and only if there is a fill-in of \(G^\prime\) with at most \(k^\prime\) edges. For planar graphs the authors obtain an \(O(k)\) kernel, and kernels of size \(O(k^{3/2})\) are obtained for graphs excluding some fixed graph as a minor and for graphs of bounded degeneracy. As a byproduct, an approximation algorithm with approximation ratio \(O(\log k)\) on planar graphs and \(O(\sqrt k\log k)\) on \(H\)-minor-free graphs is obtained.