We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of … Read more
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
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