2011/04/12 by Fedor V. Fomin, Fomin, Fedor V., Yngve Villanger +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1104.2230
23 pages, 1 figure
arxiv created 2011/04/12 · openalex publication_date 2011/04/12 · arxiv updated 2011/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time O(2^(O(k)) + k2 * 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(√(k) log k)) + k2 * nm). This substantially lower 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.