A 1.5-Approximation Algorithm for Activating Two Disjoint st-Paths

In the ActivationkDisjointst-Paths (Activationk-DP) problem we are given a graph G=(V,E) with activation costs {c_uv^u,c_uv^v} for every edge uv∈E, a source-sink pair s,t∈V, and an integer k. The goal is to compute an edge set F⊆E of k internally node disjoint st-paths of minimum activation cost ∑v∈Vmaxuv∈Fc_uv^v. The problem admits an easy 2-approximation algorithm. Alqahtani & Erlebach [1] claimed that Activation 2-DP admits a 1.5-approximation algorithm. The proof in [1] has an error, and we will show that the approximation ratio of their algorithm is at least 2. We will then give a different algorithm with approximation ratio 1.5.