Metraipolis › archive › dc_0e9859267c19

Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics — arXiv:2608.04446

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.04446
License (as archived): CC0-1.0
Archived: 2026-10-31T11:58:21.308Z
SHA-256 of the archived text: 0863d5740dc139178439336367d14f4bfb2de1a2ccbaf51948f1e64d7c9adbee
Stable URL of this page: https://metraipolis.com/documento/dc_0e9859267c19

How to cite

Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics — arXiv:2608.04446 — arXiv (en), https://arxiv.org/abs/2608.04446 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0e9859267c19 (Metraipolis archive dc_0e9859267c19, sha256 0863d5740dc139178439336367d14f4bfb2de1a2ccbaf51948f1e64d7c9adbee)

BibTeX

@misc{dc0e9859267c19,
  title = {Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics — arXiv:2608.04446},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04446},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0e9859267c19; sha256 0863d5740dc139178439336367d14f4bfb2de1a2ccbaf51948f1e64d7c9adbee},
  year = {2026}
}

Archived text

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

Treewidth is a fundamental graph invariant that quantifies how tree-like a given graph is. It is extensively used with dynamic programming to design fixed-parameter tractable algorithms for many NP-hard graph combinatorial optimization problems. However, despite broad theoretical applicability, treewidth dynamic programming (TDP) does not scale in practice beyond graphs with very small treewidth. Rather than applying TDP as a standalone technique, in this paper, we demonstrate that TDP can serve as a broadly applicable enhancer for a wide range of graph combinatorial optimization algorithms. Our framework leverages the concept of treewidth modulators, which refer to vertex sets whose removal significantly reduces the treewidth. We further propose an empirically efficient procedure for generating such treewidth modulators. To enhance an algorithm $\textit{A}$, we use $\textit{A}$ to heuristically make decisions on the modulators vertices, after which the remaining decisions outside the treewidth modulators become scalable for TDP. To demonstrate the general applicability of our proposed framework. We experimented with three classic graph combinatorial optimization models: Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms across diverse paradigms, including evolutionary search, greedy heuristics, and graph-neural-network-based heuristics. For all combinations of optimization models and base algorithms, TDP significantly improves performance over the original methods. In many settings, TDP-enhanced greedy heuristics are competitive with, and sometimes clearly outperform, state-of-the-art commercial solvers.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.04446 — 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-31T11:47:39.820Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).