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

#### Abstract

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.

#### Full Text:

PDFDOI: http://dx.doi.org/10.7146/brics.v6i49.20119

ISSN: 0909-0878

Hosted by the State and University Library and Aarhus University Library