2012/03/28 by Zeev Nutov, Nutov, Zeev · 2 citations
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.1203.6274
openalex publication_date 2012/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a k-edge-connected graph with edge costs \c(e):e ∈ E\ and let 1 ≤ ℓ ≤ k-1. We show by a simple and short proof, that G contains an ℓ-edge cover I such that: c(I) ≤ (ℓ)/(k)c(E) if G is bipartite, or if ℓ |V| is even, or if |E| ≥ (k|V|)/(2) +(k)/(2ℓ); otherwise, c(I) ≤ ((ℓ)/(k)+(1)/(k|V|))c(E). The particular case ℓ=k-1 and unit costs already includes a result of Cheriyan and Thurimella, that G contains a (k-1)-edge-cover of size |E|-\lfloor |V|/2 \rfloor. Using our result, we slightly improve the approximation ratios for the \sf k-Connected Subgraph problem (the node-connectivity version) with uniform and β-metric costs. We then consider the dual problem of finding a spanning subgraph of maximum connectivity k^* with a prescribed number of edges. We give an algorithm that computes a (k^*-1)-connected subgraph, which is tight, since the problem is NP-hard.