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?


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

  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
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Minimum_k-way_cut_in_a_hypergraph&oldid=2068"