Optimization Online


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

Bernardetta Addis(addis***at***di.unito.it)
Marco Di Summa(disumma***at***math.unipd.it)
Andrea Grosso(grosso***at***di.unito.it)

Abstract: 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 has bounded treewidth. We also extend this polynomial algorithm to several variants of the problem.

Keywords: Critical node problem, treewidth, complexity, dynamic programming

Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 07/29/2011
Entry Accepted: 07/29/2011
Entry Last Modified: 07/29/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society