We consider the Hypergraph Multiway Partition problem (Hyper-MP). The input consists of an edge-weighted hypergraph G = (V, E) and k vertices s 1 , . . . , s k called terminals. A multiway partition of the hypergraph is a partition (or labeling) of the vertices of G into k sets is the hypergraph cut function. The Hyper-MP problem asks for a multiway partition of minimum cost. Our main result is a 4/3 approximation for the Hyper-MP problem on 3-uniform hypergraphs, which is the first improvement over the (1.5−1/k) approximation of [5] . The algorithm combines the single-threshold rounding strategy of Calinescu et al. [3] with the rounding strategy of Kleinberg and Tardos [8], and it parallels the recent algorithm of Buchbinder et al. [2] for the Graph Multiway Cut problem, which is a special case. On the negative side, we show that the KT rounding scheme [8] and the exponential clocks rounding scheme [2] cannot break the (1.5 − 1/k) barrier for arbitrary hypergraphs. We give a family of instances for which both rounding schemes have an approximation ratio bounded from below by Ω( √ k), and thus the Graph Multiway Cut rounding schemes may not be sufficient for the Hyper-MP problem when the maximum hyperedge size is large. We remark that these instances have k = Θ(log n). k i=1 w(δ(A i )), where w(δ(· )) is the hypergraph cut function 1 . The Hyper-MP problem asks for a multiway partition of minimum cost. We also parameterize the problem by the maximum cardinality of a hyperedge, denoted by c; the well-studied Graph Multiway Cut problem is the special case for which c = 2. 1 For each set A ⊆ V of vertices, we use δ(A) to denote the set of all hyperedges leaving A, i.e., hyperedges e ∈ E such that A ∩ e and (V − A) ∩ e are both non-empty. We use w(δ(A)) to denote the total weight of the edges leaving A, i.e., w(δ(A)) = e∈δ(A) w(e).
Ene and Nguyen REF studied the hypergraph multiway partition problem (generalizing the graph multiway partition problem) and gave a 4/3-approximation algorithm.
From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?
ESA
Mathematics Computer Science