Critical node/edge detection problems on trees

Marco Di Summa () and Syed Md Omar Faruk
Additional contact information
Marco Di Summa: Università degli Studi di Padova
Syed Md Omar Faruk: Shahjalal University of Science and Technology

4OR, 2023, vol. 21, issue 3, No 4, 439-455

Abstract: Abstract We consider the problem of removing a limited subset of nodes and/or edges from a graph in order to minimize the so-called pairwise connectivity of the residual graph, which is defined as the total cost of the pairs of nodes still connected by a path. This is a well-studied version of a family of problems known as critical node or edge detection problems. However, while most of the literature focuses on deleting nodes or edges separately, we allow the simultaneous removal of nodes and edges. We consider both the case in which the nodes and edges removed must satisfy a joint weight limit, and the case in which two separate weight limits are given for nodes and edges. We study the complexity of several problems of this type when the given graph is a tree, providing NP-hardness results or polynomial-time algorithms for the different cases that we analyze.

Keywords: Critical node detection; Critical edge detection; Network interdiction; Pairwise connectivity; 90C27; 90C35; 90C39 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00518-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:3:d:10.1007_s10288-022-00518-0

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00518-0

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().