License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.68
URN: urn:nbn:de:0030-drops-78804
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7880/
Go to the corresponding LIPIcs Volume Portal

Tamaki, Hisao

Positive-Instance Driven Dynamic Programming for Treewidth

pdf-format:
LIPIcs-ESA-2017-68.pdf (0.5 MB)

Abstract

Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances.

We take the dynamic programming scheme due to Bouchitté and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation.

We describe the algorithm and prove its correctness. We also perform an experimental analysis counting combinatorial structures involved, which gives insights into the advantage of our approach over more conventional approaches and points to the future direction of theoretical and engineering research on treewidth computation.

BibTeX - Entry

@InProceedings{tamaki:LIPIcs:2017:7880,
  author =	{Hisao Tamaki},
  title =	{{Positive-Instance Driven Dynamic Programming for Treewidth}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{68:1--68:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7880},
  URN =		{urn:nbn:de:0030-drops-78804},
  doi =		{10.4230/LIPIcs.ESA.2017.68},
  annote =	{Keywords: treewidth, dynamic programming, minimal separators, potential maximal cliques, positive instances}
}

Keywords: treewidth, dynamic programming, minimal separators, potential maximal cliques, positive instances
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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