Fomin, Fedor V. ;
Villanger, Yngve
Searching for better fillin
Abstract
Minimum Fillin 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 NPhard.
In this paper, we study the parameterized complexity of local search for the Minimum Fillin 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 fixedparameter 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 Fillin to the list of very few problems for which local search is known to be FPT.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2013:3918,
author = {Fedor V. Fomin and Yngve Villanger},
title = {{Searching for better fillin}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {819},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3918},
URN = {urn:nbn:de:0030drops39187},
doi = {10.4230/LIPIcs.STACS.2013.8},
annote = {Keywords: Local Search, Parameterized Complexity, Fillin, Triangulation, Chordal graph}
}
2013
Keywords: 

Local Search, Parameterized Complexity, Fillin, Triangulation, Chordal graph 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

2013 