Metraipolis › archive › dc_782eb55d3a46

Treewidth and the complexity of box-constrained quadratic programs — arXiv:2609.35595

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35595
License (as archived)
CC0-1.0
Archived
2026-10-07T23:06:50.172Z
SHA-256 of the archived text
8d909e5ffb167a696d4cbf838b098b9b1b73d41a7852cd9b971f2b20f6397d3c
Stable URL of this page
https://metraipolis.com/documento/dc_782eb55d3a46

How to cite

Treewidth and the complexity of box-constrained quadratic programs — arXiv:2609.35595 — arXiv (en), https://arxiv.org/abs/2609.35595 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_782eb55d3a46 (Metraipolis archive dc_782eb55d3a46, sha256 8d909e5ffb167a696d4cbf838b098b9b1b73d41a7852cd9b971f2b20f6397d3c)
BibTeX
@misc{dc782eb55d3a46,
  title = {Treewidth and the complexity of box-constrained quadratic programs — arXiv:2609.35595},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35595},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_782eb55d3a46; sha256 8d909e5ffb167a696d4cbf838b098b9b1b73d41a7852cd9b971f2b20f6397d3c},
  year = {2026}
}

Archived text

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

We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit hypercube. We show that the situation is strikingly different. If the interaction graph is a forest, we give a strongly polynomial-time algorithm based on dynamic programming and a structural analysis of the resulting univariate value functions, which are shown to be concave and piecewise quadratic with linearly many pieces. However, the problem becomes strongly NP-hard already when the interaction graph has treewidth two. We then identify substantially more general polynomial-time solvable classes whose interaction graphs may have unbounded treewidth. Our approach exploits the fact that there exists an optimal solution in which every variable with a nonpositive coefficient for its square term is binary-valued, thereby separating the problem into a combinatorial part and a genuinely continuous part. We show that tractability can be recovered by controlling the complexity of these two parts and their interaction, rather than the treewidth of the entire interaction graph.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.35595 — 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-07T22:42:39.287Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).