Treewidth and the complexity of box-constrained quadratic programs
Abstract
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.
Related
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- Efficient ADMM for Soft-Constrained Quadratic Programs via Generalized Slack Projections
- Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
- Dynamical Systems and Nonconvex Quadratic Programs
- Open Quadratic Optimization Programs
BibTeX
@misc{pia2026treewidth,
title = {{Treewidth and the complexity of box-constrained quadratic programs}},
author = {Alberto Del Pia and Aida Khajavirad},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35595},
eprint = {2609.35595},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35595},
}
RIS
TY - UNPB
TI - Treewidth and the complexity of box-constrained quadratic programs
AU - Alberto Del Pia
AU - Aida Khajavirad
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35595
UR - https://arxiv.org/abs/2609.35595
AB - 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.
ER -