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.ICALP.2022.33
URN: urn:nbn:de:0030-drops-163740
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16374/
Go to the corresponding LIPIcs Volume Portal

Brosse, Caroline ; Limouzy, Vincent ; Mary, Arnaud

Polynomial Delay Algorithm for Minimal Chordal Completions

pdf-format:
LIPIcs-ICALP-2022-33.pdf (0.7 MB)

Abstract

Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In [Carmeli et al., 2020] (Pods 2017) Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space.
Our algorithm relies on Proximity Search, a framework recently introduced by Conte and Uno [Conte and Uno, 2019] (Stoc 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called canonical path reconstruction to design polynomial delay and polynomial space algorithms based on proximity search.

BibTeX - Entry

@InProceedings{brosse_et_al:LIPIcs.ICALP.2022.33,
  author =	{Brosse, Caroline and Limouzy, Vincent and Mary, Arnaud},
  title =	{{Polynomial Delay Algorithm for Minimal Chordal Completions}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16374},
  URN =		{urn:nbn:de:0030-drops-163740},
  doi =		{10.4230/LIPIcs.ICALP.2022.33},
  annote =	{Keywords: Graph Algorithm, Algorithmic Enumeration, Minimal chordal completions}
}

Keywords: Graph Algorithm, Algorithmic Enumeration, Minimal chordal completions
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

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