Sum of Root-Leaf Distance Interdiction Problems on Trees
摘要
This chapter explores the interdiction problems on sum of root-leaf distance on trees (Int-SRD). First, the problems (Int-SRD) under weighted \(l_1\) norm, bottleneck Hamming, and unit sum Hamming distance are solved in polynomial time and are shown to be \(\mathcal {N}\mathcal {P}\) -hard under weighted sum Hamming distance and weighted node cost. Subsequently, recognizing that the original solution does not account for the shortest root-leaf distance, a shortest path constraint is added, leading to the formulation of the double interdiction problem (DIT \(_{H\infty }\) ) and its minimal cost version. These problems are shown to be \(\mathcal {N}\mathcal {P}\) -hard and are addressed through a combination of dynamic programming and binary search algorithms in pseudo-polynomial time.