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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom