License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.8
URN: urn:nbn:de:0030-drops-39187
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3918/
Go to the corresponding LIPIcs Volume Portal

Fomin, Fedor V. ; Villanger, Yngve

Searching for better fill-in

pdf-format:
6.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fomin_et_al:LIPIcs:2013:3918,
  author =	{Fedor V. Fomin and Yngve Villanger},
  title =	{{Searching for better fill-in}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{8--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3918},
  URN =		{urn:nbn:de:0030-drops-39187},
  doi =		{10.4230/LIPIcs.STACS.2013.8},
  annote =	{Keywords: Local Search, Parameterized Complexity, Fill-in, Triangulation, Chordal graph}
}

Keywords: Local Search, Parameterized Complexity, Fill-in, Triangulation, Chordal graph
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI