The stochastic critical node problem over trees
From MaRDI portal
Abstract: We tackle a stochastic version of the Critical Node Problem (CNP) where the goal is to minimize the pairwise connectivity of a graph by attacking a subset of its nodes. In the stochastic setting considered, the attacks on nodes can fail with a certain probability. In our work we focus on trees and demonstrate that over trees the stochastic CNP actually generalizes to the stochastic Critical Element Detection Problem where attacks on edges can also fail with a certain probability. We also prove the NP-completeness of the decision version of the problem when connection costs are one, while its deterministic counterpart was proved to be polynomial. We then derive linear and nonlinear models for the considered CNP version. Moreover, we propose an exact approach based on Benders decomposition and test its effectiveness on a large set of instances. As a side result, we introduce an approximation algorithm for a problem variant of interest.
Cites work
- A genetic algorithm for a class of critical node problems
- A randomized algorithm with local search for containment of pandemic disease spread
- A survey of network interdiction models and algorithms
- Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
- An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse
- An integer programming framework for critical elements detection in graphs
- Branch and cut algorithms for detecting critical nodes in undirected graphs
- Catastrophic cascading failures in power networks
- Complexity of the critical node problem over trees
- Component-cardinality-constrained critical node problem in graphs
- Detecting critical node structures on graphs: a mathematical programming approach
- Detecting critical nodes in sparse graphs
- Deterministic network interdiction
- Epidemic dynamics on complex networks
- Exact identification of critical nodes in sparse networks via new compact formulations
- Finding the n Most Vital Nodes in a Flow Network
- Finding the most vital arcs in a network
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Improved formulations for minimum connectivity network interdiction problems
- Most vital links and nodes in weighted networks
- Network interdiction via a critical disruption path: branch-and-price algorithms
- Optimal detection of critical nodes: improvements to model structure and performance
- Partitioning procedures for solving mixed-variables programming problems
- Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- Probability chains: a general linearization technique for modeling reliability in facility location and related problems
- Reformulation and sampling to solve a stochastic network interdiction problem
- Robust critical node selection by Benders decomposition
- Robust optimization of graph partitioning and critical node detection in analyzing networks
- Shortest-path network interdiction
- Stochastic network interdiction
- The Benders decomposition algorithm: a literature review
- The critical node detection problem in networks: a survey
Cited in
(5)- Optimal Node Visitation in Stochastic Digraphs
- The critical node game
- Preprocessing and valid inequalities for exact detection of critical nodes via integer programming
- The path-variance problem on tree networks
- Optimal node visitation in acyclic stochastic digraphs with multi-threaded traversals and internal visitation requirements
This page was built for publication: The stochastic critical node problem over trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6092626)
