Treewidth and the complexity of box-constrained quadratic programs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35595
curl -X POST /api/v1/records/arxiv/2609.35595/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35595/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'