An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

Resumé

Probably most of the recent striking breakthroughs in designing approximation algorithms with provable performance guarantees are due to using novel methods of rounding polynomially solvable fractional relaxations. Applicability of the known rounding methods is highly dependent on the type of the constraints in such relaxations. In [1] the authors presented a new rounding ( pipage) method especially oriented to tackle some NP-hard problems which can be equivalently reformulated as integer programs with cardinality or a bit more general constraints. The paper [1] contains four results demonstrating
the strength of the pipage rounding. One of them is an 1/2-approximation algorithm for Max k-Cut with given sizes of parts. An instance of this problem consists of an undirected graph G = (V,E), a collection of nonnegative weights w_e associated with its edges and k positive integers p1, p2, . . . , pk such that Sum pi = |V|. It is required to find a partition of V into k parts V1, V2, . . . , Vk with each part Vi having size pi so as to maximize the total weight of edges whose ends lie in different parts of the partition. The Max
Cut and Max k-Cut problems are classical in combinatorial optimization and
have been extensively studied in the absence of cardinality constraints. The
best known approximation algorithm for Max Cut is due to Goemans and
Williamson [8] and has performance guarantee of 0.878. Frieze and Jerrum
[7] extended the technique of Goemans and Williamson to Max k-Cut and
designed a (1−1/k+2 ln k/k^2)-approximation algorithm. Few approximation
algorithms are known for some special cases of Max k-Cut with given sizes
of parts. In particular, Frieze and Jerrum [7] present an 0.65-approximation
algorithm for Max Bisection (in this problem k = 2 and p1 = p2 = |V|/2).
Very recently, Ye [9] announced an algorithm with a better performance guarantee
of 0.699. The best known approximation algorithm for Max k-Section
(in this problem p1 = ... = pk = |V|/k) is due to Andersson [2] and has
performance guarantee of 1 − 1/k + Theta(1/k^3). In this paper we consider a
natural hypergraph generalization of Max k-Cut with given sizes of parts
| - Hypergraph Max k-Cut with given sizes of parts (HMkC for short). An
instance of HMkC consists of a hypergraph H = (V,E), a collection of nonnegative
weights wS on its edges S, and k positive integers p1, . . . , pk such
that Sum pi = |V|. It is required to partition the vertex set V into k parts
(X1, . . . , Xk) with |Xi| = pi for each i, so as to maximize the total weight
of edges of H not lying wholly in any part of the partition (that is, to maximize
the total weight of edges S such that S \ Xi 6 |= 0 for each i). Several
closely related versions of Hypergraph Max k-Cut were studied in the literature
but very few results have been obtained. Andersson and Engebretsen
[3] presented an 0.72-approximation algorithm for the ordinary Hypergraph
Max Cut problem. Arora, Karger and Karpinski [4] designed a PTAS for
dense instances of this problem (i.e. in the case of hypergraphs H having
Theta(|V (H)|^d) edges) under the condition that |S| <= d for each edge S and
some constant d.
In this paper by applying the pipage rounding method we prove that
HMkC can be approximated within a factor of minfjSj : S 2 Eg of the
optimum where r = 1−(1−1=r)r−(1=r)r. By direct calculations it easy to
get some specic values of r: 2 = 1=2, 3 = 2=3 0:666, 4 = 87=128
0:679, 5 = 84=125 = 0:672, 6 0:665 and so on. It is clear that r tendsto 1 − e−1 0:632 as r ! 1. A less trivial fact is that r > 1 − e−1 for each r 3 (Lemma 2 in this paper). Adding up we arrive at the following conclusions: our algorithm nds a feasible cut of weight within a factor of 1=2 on general hypergraphs (we assume that each edge in a hypergraph has size at least 2), and within a factor of 1 − e−1 in the case when each edge has size at least 3. Note that the rst bound coincides with that we obtained in [1] for the case of graphs. In this paper we also show that in the case of hypergraphs without two-vertex edges the bound of 1 − e−1 cannot be improved unless P=NP.