Approximating k-cuts via network strength

摘要

Let G = (V, E) be an undirected connected graph with edge weights s: E → IR⁺. An edge set A ⊆ E is called a k-cut if G′ = (V,EA) has k connected components. The k-cut problem is to compute a minimum weight k-cut in G.The k-cut problem is known to be NP-hard. Saran and Vazirani [3] gave a combinatorial (2-2/k)-approximation which successively finds minimum cuts until the graph is partitioned into k components. Recently, Naor and Rabani [2] gave an integer program formulation of the problem, and showed that its integrality gap is 2.1.1 Our Contributions. We provide a new combinatorial polynomial-time approximation algorithm to the k-cut problem, with worst-case performance ratio 2. We also provide a new combinatorial lower bound, which is provably at least as good as the Naor-Rabani LP lower bound.1.2 Network Strength and Attack. For an edge set A, let k (A) denote the number of connected components in G′ = (V,EA). Define s(A) = ∑_eεA s (e). The strength of the edge set A is defined to be σ(A) := s(A)/(k(A) - 1), and the strength of the graph G is σ(G) :=min_A⊆Eσ(A). The strength of a singleton node is defined to be infinity.For an edge set A and a real number b 0, define gA(b) := s(A) - b(k(A) - 1). Let g(b) := minA⊆EgA(b) be the attack value of the network. We use e(b) to denote the edge set which achieves this minimum. Define k(b) := k(e(b)). Note that g(b) is always non-positive, since letting A = O achieves g(b) = O.Cunningham [1] provided polynomial-time algorithms to compute both the strength and the attack value of a network. We use Cunningham's algorithms as a subroutine in our algorithm.