Premium
Approximating the smallest k ‐edge connected spanning subgraph by LP‐rounding
Author(s) -
Gabow Harold N.,
Goemans Michel X.,
Tardos Éva,
Williamson David P.
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
ISBN - 0-89871-585-7
DOI - 10.1002/net.20289
Subject(s) - combinatorics , rounding , mathematics , iterated function , undirected graph , upper and lower bounds , approximation algorithm , discrete mathematics , integer (computer science) , graph , computer science , mathematical analysis , programming language , operating system
The smallest k‐ECSS problem is, given a graph along with an integer k , find a spanning subgraph that is k ‐edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/ k for undirected graphs with k > 1 odd, 1 + 2/ k for undirected graphs with k even, and 1 + 2/ k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/ k . On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 ( k ≥ 1), a polynomial‐time algorithm approximating the smallest k ‐ECSS on undirected (directed) multigraphs to within ratio 1 + c / k would imply P = NP . © 2008 Wiley Periodicals, Inc. NETWORKS, 2009