2023/07/24 by Zeev Nutov, Nutov, Zeev, Dawod Kahba +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2307.12646
openalex publication_date 2023/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Activation k Disjoint st-Paths (Activation k-DP) problem we are given a graph G=(V,E) with activation costs \cuvu,cuvv\ 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 ∈ Ecuvv. The problem admits an easy 2-approximation algorithm. Alqahtani and Erlebach [CIAC, pages 1-12, 2013] claimed that Activation 2-DP admits a 1.5-approximation algorithm. Their proof 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.