Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

References

• [1] Beideman C, Chandrasekaran K, Wang W (2021) Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. Preprint, submitted October 27, https://arxiv.org/abs/2110.14815v2.Google Scholar
• [2] Buchbinder N, Schwartz R, Weizman B (2019) A simple algorithm for the multiway cut problem. Oper. Res. Lett. 47(6):587–593.Crossref, Google Scholar
• [3] Chandrasekaran K, Chekuri C (2021) Min-max partitioning of hypergraphs and symmetric submodular functions. Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1026–1038.Google Scholar
• [4] Chandrasekaran K, Wang W (2021) Fixed parameter approximation scheme for min-max k-cut. Integer Programming and Combinatorial Optimization. IPCO, 354–367.Crossref, Google Scholar
• [5] Chandrasekaran K, Xu C, Yu X (2021) Hypergraph k-cut in randomized polynomial time. Math. Programming 186:85–113.Crossref, Google Scholar
• [6] Chekuri C, Ene A (2011) Approximation algorithms for submodular multiway partition. Proc. 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 807–816.Google Scholar
• [7] Chekuri C, Li S (2020) On the hardness of approximating the k-way hypergraph cut problem. Theory Comput. 16(14):1–8.Crossref, Google Scholar
• [8] Chekuri C, Xu C (2018) Minimum cuts and sparsification in hypergraphs. SIAM J. Comput. 47(6):2118–2156.Crossref, Google Scholar
• [9] Chekuri C, Quanrud K, Xu C (2020) LP relaxation and tree packing for minimum k-cut. SIAM J. Discrete Math. 34(2):1334–1353.Crossref, Google Scholar
• [10] Dahlhaus E, Johnson D, Papadimitriou C, Seymour P, Yannakakis M (1994) The complexity of multiterminal cuts. SIAM J. Comput. 23(4):864–894.Crossref, Google Scholar
• [11] Downey R, Estivill-Castro V, Fellows M, Prieto E, Rosamund F (2003) Cutting up is hard to do: The parameterised complexity of k-cut and related problems. Electron. Notes Theor. Comput. Sci. 78:209–222.Crossref, Google Scholar
• [12] Ene A, Vondrák J, Wu Y (2013) Local distribution and the symmetry gap: Approximability of multiway partitioning problems. Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 306–325.Google Scholar
• [13] Fox K, Panigrahi D, Zhang F (2019) Minimum cut and minimum k-cut in hypergraphs via branching contractions. Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 881–896.Google Scholar
• [14] Fukunaga T (2013) Computing minimum multiway cuts in hypergraphs. Discrete Optim. 10(4):371–382.Crossref, Google Scholar
• [15] Ghaffari M, Karger D, Panigrahi D (2017) Random contractions and sampling for hypergraph and hedge connectivity. Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1101–1114.Google Scholar
• [16] Goldschmidt O, Hochbaum D (1988) Polynomial algorithm for the k-cut problem. Proc. 29th Annual Symposium on Foundations of Computer Science, 444–451.Google Scholar
• [17] Goldschmidt O, Hochbaum D (1994) A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1):24–37.Link, Google Scholar
• [18] Guinez F, Queyranne M (2012) The size-constrained submodular k-partition problem, unpublished manuscript. https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1. See also https://smartech.gatech.edu/bitstream/handle/1853/43309/Queyranne.pdf.Google Scholar
• [19] Gupta A, Lee E, Li J (2018) An FPT algorithm beating 2-approximation for k-cut. Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2821–2837.Google Scholar
• [20] Gupta A, Lee E, Li J (2020) The Karger-Stein algorithm is optimal for k-cut. Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC), 473–484.Google Scholar
• [21] Gupta A, Harris D, Lee E, Li J (2020) Optimal bounds for the k-cut problem. Preprint, submitted May 17, https://arxiv.org/abs/2005.08301.Google Scholar
• [22] Kamidoi Y, Yoshida N, Nagamochi H (2007) A deterministic algorithm for finding all minimum k-way cuts. SIAM J. Comput. 36(5):1329–1341.Crossref, Google Scholar
• [23] Karger D (1993) Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proc. 4th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA), 21–30.Google Scholar
• [24] Karger D, Stein C (1996) A new approach to the minimum cut problem. J. ACM. 43(4):601–640.Crossref, Google Scholar
• [25] Kawarabayashi Ki, Lin B (2020) A nearly 5/3-approximation FPT algorithm for min-k-cut. Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 990–999.Google Scholar
• [26] Kawarabayashi K, Thorup M (2011) The minimum k-way cut of bounded size is fixed-parameter tractable. Proc. 52nd Annual Symposium on Foundations of Computer Science (FOCS), 160–169.Google Scholar
• [27] Lawler E (1973) Cutsets and partitions of hypergraphs. Networks 3:275–285.Crossref, Google Scholar
• [28] Li J (2019) Faster minimum k-cut of a simple graph. Proc. 60th Annual Symposium on Foundations of Computer Science (FOCS), 1056–1077.Google Scholar
• [29] Lokshtanov D, Saurabh S, Surianarayanan V (2020) A parameterized approximation scheme for min cut. Proc. 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS).Google Scholar
• [30] Manurangsi P (2017) Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. Proc. 49th Annual ACM Symposium on Theory of Computing (STOC), 954–961.Google Scholar
• [31] Manurangsi P (2018) Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the Small Set Expansion Hypothesis. Algorithms 11(1):1–10, preliminary version in Proc. ICALP 2017.Google Scholar
• [32] Marx D (2006) Parameterized graph separation problems. Theoret. Comput. Sci. 351(3):394–406.Crossref, Google Scholar
• [33] Nagamochi H, Ibaraki T (1992) A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7(1–6):583–596.Crossref, Google Scholar
• [34] Okumoto K, Fukunaga T, Nagamochi H (2012) Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62(3):787–806.Crossref, Google Scholar
• [35] Quanrud K (2019) Fast and deterministic approximations for k-cut. Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), 23:1–23:20.Google Scholar
• [36] Queyranne M (1999) On optimum size-constrained set partitions. Talk at Aussiois workshop on Combinatorial Optimization.Google Scholar
• [37] Raghavendra P, Steurer D (2010) Graph expansion and the unique games conjecture. Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC), 755–764.Google Scholar
• [38] Santiago R (2019) Multi-agent submodular optimization: variations and generalizations. Ph.D. thesis, McGill University, Montreal.Google Scholar
• [39] Saran H, Vazirani V (1995) Finding k cuts within twice the optimal. SIAM J. Comput. 24(1):101–108.Crossref, Google Scholar
• [40] Stoer M, Wagner F (1997) A simple min-cut algorithm. J. ACM. 44(4):585–591.Crossref, Google Scholar
• [41] Thorup M (2008) Minimum k-way cuts via deterministic greedy tree packing. Proc. 40th Annual ACM Symposium on Theory of Computing (STOC), 159–166.Google Scholar
• [42] Xiao M (2010) Finding minimum 3-way cuts in hypergraphs. Inform. Proc. Lett. 110(14):554–558, preliminary version in TAMC 2008.Crossref, Google Scholar
• [43] Zhao L, Nagamochi H, Ibaraki T (2005) Greedy splitting algorithms for approximating multiway partition problems. Math. Programming 102(1):167–183.Crossref, Google Scholar