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, Pierre; Scatamacchia, Rosario; Grosso, Andrea; Aringhieri, Roberto. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - ELETTRONICO. - 923:(2022), pp. 235-255. [10.1016/j.tcs.2022.05.011]
The Connected Critical Node Problem
Scatamacchia, Rosario;
2022
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.File | Dimensione | Formato | |
---|---|---|---|
ConnectedCNP.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
593.53 kB
Formato
Adobe PDF
|
593.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Connected_CNP.pdf
Open Access dal 18/05/2024
Descrizione: DOI: https://doi.org/10.1016/j.tcs.2022.05.011
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Creative commons
Dimensione
343.9 kB
Formato
Adobe PDF
|
343.9 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2974513