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?
For graphs, Goldschmidt and Hochbaum  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 .
The hypergraph case seems considerably more difficult. Xiao  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  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 . For symmetric submodular functions, this and another algorithm by Nagamochi and Ibaraki  can be exended to the k=4 case , 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 , who gave a 4/3-approximation for 3-regular hypergraphs. A far-reaching generalization is the submodular multiway partition problem; Chekuri and Ene  gave a 2-approximation algorithm for this, and a [math](1.5-1/k)[/math]-approximation if the submodular function is symmetric.
- 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