treewidth

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

  • Bernardetta Addis
  • Marco Di Summa
  • Andrea Grosso
    • Categories Combinatorial Optimization Tags , , ,

    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

  • Hans L. Bodlaender
  • Arie M.C.A. Koster
  • Stan P.M. van Hoesel
    • Categories Graphs and Matroids Tags , , ,

    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