Metraipolis › archive › dc_baff7b79161a

Output-linear time enumeration of potential maximal cliques — arXiv:2610.19850

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19850
License (as archived)
CC0-1.0
Archived
2026-10-15T21:58:26.904Z
SHA-256 of the archived text
75e80ac56551083ac3d7e52957da00f9ccba4c81ebb7165f46d71eaf4c6bae97
Stable URL of this page
https://metraipolis.com/documento/dc_baff7b79161a

How to cite

Output-linear time enumeration of potential maximal cliques — arXiv:2610.19850 — arXiv (en), https://arxiv.org/abs/2610.19850 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_baff7b79161a (Metraipolis archive dc_baff7b79161a, sha256 75e80ac56551083ac3d7e52957da00f9ccba4c81ebb7165f46d71eaf4c6bae97)
BibTeX
@misc{dcbaff7b79161a,
  title = {Output-linear time enumeration of potential maximal cliques — arXiv:2610.19850},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19850},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_baff7b79161a; sha256 75e80ac56551083ac3d7e52957da00f9ccba4c81ebb7165f46d71eaf4c6bae97},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19850. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, {\em i.e.} a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.19850 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:39:44.499Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).