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 (weighted or unweighted) number of connections between pairs of nodes in the residual graph. In particular, we study the case where the physical network represented by graph G has a hierarchical organization, so that G is a tree. The NP‐completenessNP‐completeness of this problem for general graphs has been already established (Arulselvan et al.). We study the subclass of CNP over trees, generalizing the objective function and constraints to take into account general nonnegative “costs” of node connections and “weights” for the nodes that are to be removed. We prove that CNP over trees is still NP‐completeNP‐complete when general connection costs are specified, while the cases where all connections have unit cost are solvable in polynomial time by dynamic programming approaches. For the case with nonnegative connection costs and unit node weights we propose an enumeration scheme whose time complexity is within a polynomial factor from O(1.618034n), where n is the number of nodes of the tree. Results from computational experiments are reported for all the proposed algorithms.

Complexity of the critical node problem over trees

GROSSO, Andrea Cesare;LOCATELLI, Marco
2011

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 (weighted or unweighted) number of connections between pairs of nodes in the residual graph. In particular, we study the case where the physical network represented by graph G has a hierarchical organization, so that G is a tree. The NP‐completenessNP‐completeness of this problem for general graphs has been already established (Arulselvan et al.). We study the subclass of CNP over trees, generalizing the objective function and constraints to take into account general nonnegative “costs” of node connections and “weights” for the nodes that are to be removed. We prove that CNP over trees is still NP‐completeNP‐complete when general connection costs are specified, while the cases where all connections have unit cost are solvable in polynomial time by dynamic programming approaches. For the case with nonnegative connection costs and unit node weights we propose an enumeration scheme whose time complexity is within a polynomial factor from O(1.618034n), where n is the number of nodes of the tree. Results from computational experiments are reported for all the proposed algorithms.
38
1766
1774
M. Di Summa; A. Grosso; M. Locatelli
File in questo prodotto:
File Dimensione Formato  
cnpCOR.pdf

Accesso aperto

Descrizione: Articolo principale
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 532.86 kB
Formato Adobe PDF
532.86 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/133531
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 60
  • ???jsp.display-item.citation.isi??? 51
social impact