treewidth – Optimization Online

A polynomial-time solvable class of sparse box-constrained polynomial optimization problems

Published: 2026/04/28, Updated: 2026/08/20

Aida Khajavirad

(Mixed) Integer Nonlinear Programming binary polynomial optimization, box-constrained polynomial optimization, hypergraph, polynomial-time algorithm, sparsity, treewidth

We study the problem of minimizing a multivariate polynomial function over the unit hypercube. Exploiting sparsity in the interaction graph or hypergraph, we identify variables that can be restricted to binary values at optimality and eliminate the remaining continuous variables component-wise, reducing the problem to structured binary polynomial optimization. For quadratic objectives, we obtain exact … Read more

Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

Published: 2011/07/29

Combinatorial Optimization complexity, critical node problem, dynamic programming, treewidth

We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more

Treewidth: Computational Experiments

Published: 2002/01/17

Graphs and Matroids computations, heuristics, lower bounds, treewidth

Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many optimization … Read more