Double interdiction problem on trees on the sum of root-leaf distances by upgrading edges

Xiao Li (), Xiucui Guan (), Junhua Jia () and Panos M. Pardalos ()
Additional contact information
Xiao Li: Southeast University
Xiucui Guan: Southeast University
Junhua Jia: Southeast University
Panos M. Pardalos: University of Florida

Journal of Global Optimization, 2025, vol. 92, issue 4, No 5, 972 pages

Abstract: Abstract The double interdiction problem on trees (DIT) for the sum of root-leaf distances (SRD) has significant implications in diverse areas such as transportation networks, military strategies, and counter-terrorism efforts. It aims to maximize the SRD by upgrading edge weights subject to two constraints. One gives an upper bound for the cost of upgrades under certain norm and the other specifies a lower bound for the shortest root-leaf distance (StRD). We utilize both weighted $$l_\infty $$ l ∞ norm and Hamming distance to measure the upgrade cost and denote the corresponding (DIT) problem by ( $$\hbox {DIT}_{H\infty }$$ DIT H ∞ ) and its minimum cost problem by ( $$\hbox {MCDIT}_{H\infty }$$ MCDIT H ∞ ). We establish the $$\mathcal{N}\mathcal{P}$$ N P -hardness of problem ( $$\hbox {DIT}_{H\infty }$$ DIT H ∞ ) by building a reduction from the 0–1 knapsack problem. We solve the problem ( $$\hbox {DIT}_{H\infty }$$ DIT H ∞ ) by two scenarios based on the number N of upgrade edges. When $$N=1$$ N = 1 , a greedy algorithm with O(n) complexity is proposed. For the general case, an exact dynamic programming algorithm within a pseudo-polynomial time is proposed, which is established on a structure of left subtrees by maximizing a convex combination of the StRD and SRD. Furthermore, we confirm the $$\mathcal{N}\mathcal{P}$$ N P -hardness of problem ( $$\hbox {MCDIT}_{H\infty }$$ MCDIT H ∞ ) by reducing from the 0–1 knapsack problem. To tackle problem ( $$\hbox {MCDIT}_{H\infty }$$ MCDIT H ∞ ), a binary search algorithm with pseudo-polynomial time complexity is outlined, which iteratively solves problem ( $$\hbox {DIT}_{H\infty }$$ DIT H ∞ ). We culminate our study with numerical experiments, showcasing effectiveness of the algorithm.

Keywords: Network interdiction problem; Upgrade critical edges; Shortest path; Sum of root-leaf distance; Dynamic programming algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01490-9 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:jglopt:v:92:y:2025:i:4:d:10.1007_s10898-025-01490-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01490-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().