2021/11/07 by Nutov, Zeev
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.04011
In activation network design problems we are given an undirected graph G=(V,E) and a pair of activation costs \ceu,cev\ for each e=uv ∈ E. The goal is to find an edge set F ⊆ E that satisfies a prescribed property of minimum activation cost τ(F)=∑v ∈ V max \cev: e ∈ F is incident to v\. In the Activation k Disjoint Paths problem we are given s,t ∈ V and an integer k, and seek an edge set F ⊆ E of k internally disjoint st-paths of minimum activation cost. The problem admits an easy 2-approximation algorithm. However, it was an open question whether the problem is in P even for k=2 and power activation costs, when ceu=cev for all e=uv ∈ E. Here we will answer this question by giving a polynomial time algorithm using linear programing. We will also mention several consequences, among them a polynomial time algorithm for the Activation 2 Edge Disjoint Paths problem, and improved approximation ratios for the Min-Power k-Connected Subgraph problem.