Small ? ? -edge-covers in k k -connected graphs
Let G=(V,E) G = ( V , E ) be a k k -edge-connected graph with edge-costs {c(e):e?E} { c ( e ) : e ? E } and minimum degree d d . We show by a simple and short proof, that for any integer ? ? with d k ? ? ? d ( 1 ? 1 k ) , G G contains an ? ? -edge cover I I such that: c ( I ) ? ? d c ( E ) if G G is bipartite, or if ?|V| ? | V | is even, or if | E | ? d | V | 2 + d 2 ? ; otherwise, c ( I ) ? ( ? d + 1 d | V | ) c ( E ) . The particular case d=k=?+1 d = k = ? + 1 and unit costs already includes a result of Cheriyan and Thurimella (2000) [1], that G G contains a (k?1) ( k ? 1 ) -edge-cover of size |E|??|V|/2? | E | ? ? | V | / 2 ? . Using our result, we slightly improve the approximation ratios for the k 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? k ? with a prescribed number of edges. We give an algorithm that computes a (k??1) ( k ? ? 1 ) -connected subgraph, which is tight, since the problem is NP-hard.
k k -edge-cover k k k k k k k -connectivity k k k k k approximation algorithms