SUBEXPONENTIAL PARAMETERIZED ALGORITHM FOR MINIMUM FILL-IN

The MINIMUM FILL-IN problem is used to decide if a graph can be triangulated by adding at most k edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time O(2(O(k)) + k(2)nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving MINIMUM FILL-IN in time O(2(O(root k log k)) + k(2)nm). This substantially lowers the complexity of the problem. Techniques developed for MINIMUM FILL-IN can be used to obtain subexponential parameterized algorithms for several related problems, including MINIMUM CHAIN COMPLETION, CHORDAL GRAPH SANDWICH, and TRIANGULATING COLORED GRAPH.