Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper investigates whether the classical bounded-treewidth tractability of binary quadratic programming transfers to box-constrained quadratic programs over the unit hypercube. The authors prove a sharp complexity threshold: tree-structured interactions are solvable in strongly polynomial time via dynamic programming, but the problem immediately becomes strongly NP-hard at treewidth two. Crucially, they show that tractability can still be recovered on select unbounded-treewidth graphs by decoupling variables with nonpositive quadratic terms into extreme binary values to separate combinatorial and continuous sub-problems.
Continuous relaxations can be strictly harder than discrete optimization: box-constrained quadratic programming collapses into strong NP-hardness at treewidth two, breaking the universal bounded-treewidth tractability enjoyed by binary QPs.
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.