License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.17
URN: urn:nbn:de:0030-drops-165512
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16551/
Go to the corresponding LIPIcs Volume Portal

Tamaki, Hisao

Heuristic Computation of Exact Treewidth

pdf-format:
LIPIcs-SEA-2022-17.pdf (0.7 MB)

Abstract

We are interested in computing the treewidth tw(G) of a given graph G. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to tw(G) from both sides. The upper bound algorithm extends and simplifies the present author’s unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitté and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor H of G, we have tw(H) ≤ tw(G). Starting from a greedily computed minor H_0 of G, the algorithm tries to construct a sequence of minors H_0, H_1, ..., H_k with tw(H_i) < tw(H_{i + 1}) for 0 ≤ i < k and hopefully tw(H_k) = tw(G).
We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.

BibTeX - Entry

@InProceedings{tamaki:LIPIcs.SEA.2022.17,
  author =	{Tamaki, Hisao},
  title =	{{Heuristic Computation of Exact Treewidth}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16551},
  URN =		{urn:nbn:de:0030-drops-165512},
  doi =		{10.4230/LIPIcs.SEA.2022.17},
  annote =	{Keywords: graph algorithm, treewidth, heuristics, BT dynamic programming, contraction, obstruction, minimal forbidden minor, certifying algorithms}
}

Keywords: graph algorithm, treewidth, heuristics, BT dynamic programming, contraction, obstruction, minimal forbidden minor, certifying algorithms
Collection: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue Date: 2022
Date of publication: 11.07.2022

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