The Critical Node Problem is a well-known optimisation problem that aims to find the subset of nodes in a graph whose removal impacts the graph connectivity as much as possible according to a specific connectivity measure. In this work, we study a new version of the Critical Node Problem, which we call the Connected Critical Node Problem, where the set of the removed nodes has to form a connected subgraph. We consider three connectivity measures and provide complexity results and solution approaches for general graphs and specific classes of graphs such as graphs with bounded treewidth, trees and series-parallel graphs. We consider the Connected Critical Node Problem where the pairwise connectivity (related to the number of pairs of vertices still connected in the graph) is minimised. We prove that this problem is strongly NP-hard and inapproximable on general graphs and is polynomial-time solvable on graphs with bounded treewidth and with unit connection costs. Further, we prove the NP-hardness of the problem with arbitrary connection costs over trees and series-parallel graphs and derive dynamic programming algorithms. We extend our results to the problem variants that consider the minimisation of the largest connected component and the maximisation of the number of connected components (also called K-way Vertex Cut Problem). As side results, we provide new complexity results for the classic Critical Node Problem on series-parallel graphs.

The Connected Critical Node Problem

Hosteins P.;Grosso A.;Aringhieri R.
2022-01-01

Abstract

The Critical Node Problem is a well-known optimisation problem that aims to find the subset of nodes in a graph whose removal impacts the graph connectivity as much as possible according to a specific connectivity measure. In this work, we study a new version of the Critical Node Problem, which we call the Connected Critical Node Problem, where the set of the removed nodes has to form a connected subgraph. We consider three connectivity measures and provide complexity results and solution approaches for general graphs and specific classes of graphs such as graphs with bounded treewidth, trees and series-parallel graphs. We consider the Connected Critical Node Problem where the pairwise connectivity (related to the number of pairs of vertices still connected in the graph) is minimised. We prove that this problem is strongly NP-hard and inapproximable on general graphs and is polynomial-time solvable on graphs with bounded treewidth and with unit connection costs. Further, we prove the NP-hardness of the problem with arbitrary connection costs over trees and series-parallel graphs and derive dynamic programming algorithms. We extend our results to the problem variants that consider the minimisation of the largest connected component and the maximisation of the number of connected components (also called K-way Vertex Cut Problem). As side results, we provide new complexity results for the classic Critical Node Problem on series-parallel graphs.
2022
923
235
255
https://www.sciencedirect.com/science/article/pii/S0304397522003115
Hosteins P.; Scatamacchia R.; Grosso A.; Aringhieri R.
File in questo prodotto:
File Dimensione Formato  
2022-TCS-CNP-published.pdf

Accesso riservato

Descrizione: Published version
Tipo di file: PDF EDITORIALE
Dimensione 593.53 kB
Formato Adobe PDF
593.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2022-TCS-CNP-postprint.pdf

Open Access dal 17/05/2024

Descrizione: Post print
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 535.74 kB
Formato Adobe PDF
535.74 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/1879002
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact