Interdiction Models and Heuristics for Graph Propagation
Networks · 2026-05-14
DOI: 10.1002/net.70047 ↗At a glance
Journal article in Networks, published online on 2026-05-14. Written by Agostinho Agra and 1 co-authors. 37 references. The full text is freely available (open access, CC BY 4.0). Funded by: Fundação para a Ciência e a Tecnologia.
Abstract (original language)
Given a graph and a set of activated/infected nodes, we consider the problem of determining the set of nodes that minimizes the network propagation on the subgraph that results from the removal of those nodes. To measure network propagation, we assume that a node is activated/infected in the resulting subgraph if there is a path from an activated/infected node in to node . Several mixed‐integer programs are presented to find the critical nodes to prevent propagation on directed and undirected graphs. Two compact models are devised by adapting the best‐known models for determining a set of critical nodes in a graph to this problem. A new compact model is devised from a network interdiction formulation, and a new path‐formulation model is introduced. We show that all the models provide the same linear relaxation bound and compare them on a set of instances from the literature. To address the computational challenges of large networks, several efficient heuristics are introduced. The results show that the compact model from the interdiction perspective is faster, allowing it to solve to optimality sparse networks with up to 10 000 nodes.
Funding
- Fundação para a Ciência e a Tecnologia
Cite
APA
Agra, A., & Samuco, J. M. (2026). Interdiction Models and Heuristics for Graph Propagation. Networks. https://doi.org/10.1002/net.70047
Vancouver
Agra A, Samuco JM. Interdiction Models and Heuristics for Graph Propagation. Networks. 2026. doi:10.1002/net.70047
BibTeX
@article{Agra2026,
author = {Agra, Agostinho and Samuco, José Maria},
title = {Interdiction Models and Heuristics for Graph Propagation},
journal = {Networks},
year = {2026},
doi = {10.1002/net.70047}
}
EUVIMED