# Minimum k-way cut in a hypergraph

Can we find a minimum *k*-way cut in a capacitated hypergraph in polynomial time, if *k* is fixed?

## Remarks

For graphs, Goldschmidt and Hochbaum ^{[1]} showed that finding a minimum *k*-way cut is NP-hard if *k* is not fixed, and solvable in polynomial time if *k* is fixed. The currently fastest algorithm for graphs is by Thorup ^{[2]}.

The hypergraph case seems considerably more difficult. Xiao ^{[3]} gave a polynomial time algorithm for *k*=3, but no algorithm is known for *k*=4.
If the rank (maximum size of hyperedges) of the hypergraph is fixed, then there is a polynomial algorithm by Fukunaga ^{[4]} which extends the techniques of Thorup to hypergraphs.

The algorithm of Xiao for *k=3* can be extended to the more general submodular *k*-way partition problem ^{[5]}. For symmetric submodular functions, this and another algorithm by Nagamochi and Ibaraki ^{[6]} can be exended to the *k=4* case ^{[7]}, but the *k=5* case is already open.

## Minimum multiway cuts

The minimum multiway cut problem (when *k* terminals are also given) is APX-hard even for [math]k=3[/math] in graphs. The hypergraph case was studied by Ene and Nguyen ^{[8]}, who gave a 4/3-approximation for 3-regular hypergraphs. A far-reaching generalization is the submodular multiway partition problem; Chekuri and Ene ^{[9]} gave a 2-approximation algorithm for this, and a [math](1.5-1/k)[/math]-approximation if the submodular function is symmetric.

## References

- ↑ O. Goldschmidt and D. Hochbaum,
*A polynomial algorithm for the k-cut problem for fixed k*, Mathematics of Operations Research, 19 (1994), 24-37. DOI link - ↑ M. Thorup,
*Minimum k-way cuts via deterministic greedy tree packing*, In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), 159–166. DOI link - ↑ M. Xiao,
*Finding minimum 3-way cuts in hypergraphs*, In Theory and Applications of Models of Computation: Proceedings of the 5th International Conference, LNCS 4978 (2008), 270–281. DOI link - ↑ T. Fukunaga,
*Computing minimum multiway cuts in hypergraphs from hypertree packings*, Author link, DOI link - ↑ K. Okumoto, T. Fukunaga, H. Nagamochi,
*Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems*, DOI link, Technical report link - ↑ H. Nagamochi, T. Ibaraki,
*A fast algorithm for computing minimum 3-way and 4-way cuts*, DOI link - ↑ M. Queyranne, F. Guinez,
*The size-constrained submodular k-partition problem*, manuscript, author link, slides - ↑ A. Ene, L. Nguyen,
*From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?*, DOI link - ↑ C. Chekuri, A. Ene,
*Approximation Algorithms for Submodular Multiway Partition*, arXiv link