Optimization Online


Complexity of the Critical Node Problem over trees

Marco Di Summa (disumma***at***di.unito.it)
Andrea Grosso (grosso***at***di.unito.it)
Marco Locatelli (locatell***at***ce.unipr.it)

Abstract: In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established in [1], here we study the subclass of CNP over trees. We will prove that weighted CNP over trees is still NP-complete, while the unweighted version can be proved to be solvable in polynomial time through a dynamic programming approach.

Keywords: Complexity, Critical Node Problem, Multicut in Trees, Dynamic Programming

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation: [1] Arulselvan A., Commander C.W., Elefteriadou L., Pardalos P.M., Detecting critical nodes in sparse graphs, Computers & Operations Research, 36, 2193220 (2009)

Download: [PDF]

Entry Submitted: 02/12/2010
Entry Accepted: 02/12/2010
Entry Last Modified: 02/12/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 Programming Society