Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Gaspers, Serge; Gudmundsson, Joachim; Jones, Mitchell; Mestre, Julián; Rümmele, Stefan http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-69322
URL:

; ; ; ;

Turbocharging Treewidth Heuristics

pdf-format:


Abstract

A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for quality of the solution.

BibTeX - Entry

@InProceedings{gaspers_et_al:LIPIcs:2017:6932,
  author =	{Serge Gaspers and Joachim Gudmundsson and Mitchell Jones and Juli{\'a}n Mestre and Stefan R{\"u}mmele},
  title =	{{Turbocharging Treewidth Heuristics}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6932},
  URN =		{urn:nbn:de:0030-drops-69322},
  doi =		{10.4230/LIPIcs.IPEC.2016.13},
  annote =	{Keywords: tree decomposition, heuristic, fixed-parameter tractability, local search}
}

Keywords: tree decomposition, heuristic, fixed-parameter tractability, local search
Seminar: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue date: 2017
Date of publication: 2017


DROPS-Home | Fulltext Search | Imprint Published by LZI