Network Resilience and the Length-Bounded Multicut Problem
Abstract
Motivated by networked systems in which the functionality of the network depends on vertices in the network being within a bounded distance T of each other, we study the length-bounded multicut problem: given a set of pairs, find a minimum-size set of edges whose removal ensures the distance between each pair exceeds T . We introduce the first algorithms for this problem capable of scaling to massive networks with billions of edges and nodes: three highly scalable algorithms with worst-case performance ratios. Furthermore, one of our algorithms is fully dynamic, capable of updating its solution upon incremental vertex / edge additions or removals from the network while maintaining its performance ratio. Finally, we show that unless NP ⊆ BPP , there is no polynomial-time, approximation algorithm with performance ratio better than $Ømega (T)$, which matches the ratio of our dynamic algorithm up to a constant factor.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 03, 2018
- Source ID
- 10.1145/3179407
Entities
People
- Alan Kuhnle
- My T Thai
- Victoria G. Crawford
Organizations
- Defense Threat Reduction Agency
- National Science Foundation
- University of Florida