Maximum Shortest Path Interdiction Problem by Upgrading Nodes on Trees under Unit Cost

Qiao Zhang, Xiao Li, Xiucui Guan, Pãnos M. PardalosarXiv 2025 · DOI · arXiv

TL;DR

This paper shifts the focus of network interdiction from "deleting" nodes to "upgrading" them—essentially increasing the resistance or travel time through specific points to maximize the shortest path length. The authors provide an efficient $O(n^3)$ dynamic programming algorithm to solve this on tree structures under unit costs, offering a practical framework for scenarios like wildfire containment where total elimination of risk is impossible.

What Problem Does This Paper Address?

In classical network interdiction, an "interdictor" tries to disrupt a network (like a supply chain or a communication grid) by removing a set of critical nodes or edges to make the shortest path between two points as long as possible. However, in many real-world scenarios—such as managing wildfires or slowing the spread of a virus—completely "deleting" a node is either impossible or prohibitively expensive.

The authors tackle the Maximum Shortest Path Interdiction Problem by Upgrading Nodes (MSPIT-UN). Instead of removing a node, you "upgrade" it, which increases the length of the edges connected to it (think of this as adding fire retardant to a forest zone to slow a fire's progress). The goal is to choose a subset of nodes to upgrade, within a fixed budget, to maximize the shortest distance from the root of a tree to any of its leaves. They also address the "dual" problem: what is the minimum number of nodes we need to upgrade to ensure the shortest path is at least a certain length $D$?

Methods

The researchers focus on rooted trees under a unit cost assumption (every node upgrade costs exactly 1 unit). This specific structure allows them to move away from the NP-hard complexity often found in general graph interdiction.

Key methodological highlights include:

  • Tree Decomposition: The authors define "layers" and "chains" within the tree. A chain is a path between a node and its "critical ancestor" (a node with a branching factor greater than two).
  • Dynamic Programming (DP): They develop a DP algorithm based on a "left $q$-subtree" structure. By processing the tree from the leaves up to the root, the algorithm builds optimal solutions for sub-problems. It calculates the maximum shortest path distance for a given budget $K$ by considering two cases for every node: whether it is upgraded or not.
  • Binary Search Integration: To solve the minimum cost problem (MCSPIT-UN$_u$), the authors wrap their DP algorithm in a binary search. Since the shortest path length is monotonic with respect to the number of upgrades, they can efficiently find the smallest $K$ that meets the distance requirement.

Datasets

The paper uses randomly generated tree instances for evaluation.

  • Scale: Trees ranging from 100 to 3,000 vertices.
  • Parameters: Edge weights ($w$) and upgraded weights ($u$) were generated randomly such that $0 \leq w \leq u$.
  • Environment: Simulations were conducted in MATLAB 2025a on a standard consumer-grade CPU (Intel i7).

Key Insights and Ideas

  • The "Upgrade" Philosophy: The most significant insight is the shift from binary "exist/not-exist" interdiction to a "degradation" model. This is much more representative of fields like disaster management or traffic control.
  • Complexity Reduction: Previous work on similar problems under different cost norms resulted in $O(n^4)$ complexities. By focusing on the unit cost and tree topology, the authors successfully reduced the complexity to $O(n^3)$.
  • Structural Exploitation: The algorithm's efficiency comes from recognizing that on a tree, the shortest path to any leaf must pass through a specific sequence of "critical" nodes. This allows the DP to focus only on these bottleneck points rather than every possible path combination.

Key Results

  • Algorithmic Efficiency: The MSPIT-UN$_u$ problem is solved in $O(n^3)$ time, while the minimum cost version is solved in $O(n^3 \log n)$.
  • Numerical Performance: In practical tests, the $O(n^3)$ algorithm was remarkably fast. For a tree with 1,000 nodes, the average execution time was approximately 1.7 seconds. Even at the 3,000-node scale, it completed in under 50 seconds.
  • Scalability: The results showed that the execution time scales predictably with the theoretical complexity, confirming that the algorithm is suitable for relatively large-scale tree networks.

Limitations and Future Work

While the paper makes a strong case for tree-based networks, it has a few notable limitations:

  • Topology Constraints: The current algorithms are strictly for trees. Real-world networks (like road maps or power grids) are often cyclic. The authors suggest extending this to "series-parallel" graphs or general graphs in the future.
  • Unit Cost Assumption: The $O(n^3)$ efficiency relies on each upgrade costing the same. In reality, upgrading a major transit hub is likely more expensive than a rural outpost. Future research could look at variable cost vectors.
  • Deterministic Weights: The model assumes we know exactly how much an upgrade will slow things down. Incorporating stochastic (uncertain) travel times would be a valuable next step for robustness.

Summary updated

Abstract

Network interdiction problems by deleting critical nodes have wide applications. However, node deletion is not always feasible in certain practical scenarios. We consider the maximum shortest path interdiction problem by upgrading nodes on trees under unit cost (MSPIT-UN$_u$). It aims to upgrade a subset of nodes to maximize the length of the shortest root-leaf distance such that the total upgrade cost under unit cost is upper bounded by a given value. We develop a dynamic programming algorithm with a time complexity of $O(n^3)$ to solve this problem. Furthermore, we consider the related minimum cost problem of (MSPIT-UN$_u$) and propose an $O(n^3\log n)$ binary search algorithm, where a dynamic programming algorithm is exceeded in each iteration to solve its corresponding problem (MSPIT-UN$_u$). Finally, we design numerical experiments to show the effectiveness of the algorithms.
BibTeX
@misc{zhang2025maximum,
  author = {Qiao Zhang and Xiao Li and Xiucui Guan and Pãnos M. Pardalos},
  title = {{Maximum Shortest Path Interdiction Problem by Upgrading Nodes on Trees under Unit Cost}},
  year = {2025},
  eprint = {2504.05190},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.05190},
  howpublished = {arXiv},
}
Figure