k disjoint st-paths activation in polynomial time
share
In activation network design problems we are given an undirected graph G=(V,E) and a pair of activation costs {c_e^u,c_e^v} 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 ∈ Vmax{c_e^v: e ∈ F 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 c_e^u=c_e^v 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.
READ FULL TEXT