Minimum k-way cut in a hypergraph

From Egres Open
Jump to: navigation, search

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


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.


  1. 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
  2. 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
  3. 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
  4. T. Fukunaga, Computing minimum multiway cuts in hypergraphs from hypertree packings, Author link, DOI link
  5. K. Okumoto, T. Fukunaga, H. Nagamochi, Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, DOI link, Technical report link
  6. H. Nagamochi, T. Ibaraki, A fast algorithm for computing minimum 3-way and 4-way cuts, DOI link
  7. M. Queyranne, F. Guinez, The size-constrained submodular k-partition problem, manuscript, author link, slides
  8. A. Ene, L. Nguyen, From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?, DOI link
  9. C. Chekuri, A. Ene, Approximation Algorithms for Submodular Multiway Partition, arXiv link