2026-07-24T11:17:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3918 2024-03-06T10:34:37Z ddc:004 open_access

Searching for better fill-in Fomin, Fedor V. Villanger, Yngve Local Search Parameterized Complexity Fill-in Triangulation Chordal graph Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. By the classical result of Rose, Tarjan, Lueker, and Ohtsuki from 1976, an inclusion minimal triangulation of a graph can be found in polynomial time but, as it was shown by Yannakakis in 1981, finding a triangulation with the minimum number of edges is NP-hard. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation by providing an algorithm that in time O(f(k) |G|^{O(1)}) decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Yngve Villanger 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.8 urn:nbn:de:0030-drops-39187 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.8 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode