Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k

References

• [1] Abboud A, Krauthgamer R, Trabelsi O (2021) Subcubic algorithms for Gomory–Hu tree in unweighted graphs. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1725–1737.Google Scholar
• [2] Ahn K, Guha S (2009) Graph sparsification in the semi-streaming model. Proc. 36th Internat. Colloquium Automata Languages Programming Part II (Springer, Berlin, Heidelberg), 328–338.Google Scholar
• [3] Ahn K, Guha S, McGregor A (2012) Analyzing graph structure via linear measurements. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 459–467.Google Scholar
• [4] Ahn K, Guha S, McGregor A (2012) Graph sketches: Sparsification, spanners, and subgraphs. Proc. 31st Sympos. Principles Database Systems (ACM, New York), 5–14.Google Scholar
• [5] Applegate D, Bixby R, Chvátal V, Cook W (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• [6] Bansal N, Svensson O, Trevisan L (2019) New notions and constructions of sparsification for graphs and hypergraphs. Proc. 60th Annual IEEE Sympos. Foundations Comput. Sci., 910–928.Google Scholar
• [7] Beideman C, Chandrasekaran K, Wang W (2022) Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. Proc. 33rd Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 2208–2228.Google Scholar
• [8] Beideman C, Chandrasekaran K, Wang W (2023) Approximate minimum cuts and their enumeration. Sympos. Simplicity Algorithms, 36–41.Google Scholar
• [9] Benczur A (1995) A representation of cuts within 6/5 times the edge connectivity with applications. Proc. 36th Annual IEEE Foundations Comput. Sci. (IEEE, Piscataway, NJ), 92–102.Google Scholar
• [10] Benczur A (1997) Cut structures and randomized algorithms in edge-connectivity problems. Unpublished PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• [11] Benczur A, Goemans M (2008) Deformable polygon representation and near-mincuts. Groetschel M, Katona GOH, eds. Building Bridges: Between Mathematics and Computer Science, Bolyai Society Mathematical Studies, vol. 19 (Springer, New York), 103–135.Crossref, Google Scholar
• [12] Chandrasekaran K, Chekuri C (2021) Min-max partitioning of hypergraphs and symmetric submodular functions. Proc. 32nd Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 1026–1038.Google Scholar
• [13] Chandrasekaran K, Chekuri C (2022) Hypergraph k-cut for fixed k in deterministic polynomial time. Math. Oper. Res. 47(4):3380–3399.Link, Google Scholar
• [14] Chandrasekaran K, Wang W (2023) Fixed parameter approximation scheme for min-max k-cut. Math. Programming 197:1093–1144.Google Scholar
• [15] Chandrasekaran K, Zhang X (2020) Hardness of min-max hypergraph k-partition when k is part of input, Personal communication.Google Scholar
• [16] Chandrasekaran K, Xu C, Yu X (2021) Hypergraph k-cut in randomized polynomial time. Math. Programming 186:85–113.Crossref, Google Scholar
• [17] 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
• [18] Chekuri C, Xu C (2018) Minimum cuts and sparsification in hypergraphs. SIAM J. Comput. 47(6):2118–2156.Crossref, Google Scholar
• [19] 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
• [20] Chen Y, Khanna S, Nagda A (2020) Near-linear size hypergraph cut sparsifiers. Proc. 61st Annual IEEE Sympo. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 61–72.Google Scholar
• [21] Cook W, Cunningham W, Pulleyblank W, Schrijver A (1997) Combinatorial Optimization (Wiley, Hoboken, NJ).Crossref, Google Scholar
• [22] Dinitz EA, Karzanov AV, Lomonosov MV (1976) On the structure of a family of minimum weighted cuts in a graph. Fridman AA, ed. Studies in Discrete Optimization (Nauka Publishers, Moscow).Google Scholar
• [23] 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. Electronic Notes Theoretical Comput. Sci. 78:209–222.Crossref, Google Scholar
• [24] Fox K, Panigrahi D, Zhang F (2019) Minimum cut and minimum k-cut in hypergraphs via branching contractions. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 881–896.Google Scholar
• [25] Ghaffari M, Karger D, Panigrahi D (2017) Random contractions and sampling for hypergraph and hedge connectivity. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 1101–1114.Google Scholar
• [26] Goemans MX, Ramakrishnan VS (1995) Minimizing submodular functions over families of sets. Combinatorica 15(4):499–513.Crossref, Google Scholar
• [27] 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
• [28] Guinez F, Queyranne M (2012) The size-constrained submodular k-partition problem. Accessed 2021, https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1.Google Scholar
• [29] Gupta A, Lee E, Li J (2018) An FPT algorithm beating 2-approximation for k-cut. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 2821–2837.Google Scholar
• [30] Gupta A, Lee E, Li J (2018) Faster exact and approximate algorithms for k-cut. Proc. 59th IEEE Annual Sympo. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 113–123.Google Scholar
• [31] Gupta A, Lee E, Li J (2019) The number of minimum k-cuts: Improving the Karger-Stein bound. Proc. 51st ACM Sympos. Theory Comput. (ACM, New York), 229–240.Google Scholar
• [32] Gupta A, Lee E, Li J (2020) The Karger-Stein algorithm is optimal for k-cut. Proc. 52nd Annual ACM Sympos. Theory Comput. (ACM, New York), 473–484.Google Scholar
• [33] 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
• [34] Henzinger M, Williamson D (1996) On the number of small cuts in a graph. Inform. Processing Lett. 59(1):41–44.Crossref, Google Scholar
• [35] Hirayama T, Liu Y, Makino K, Shi K, Xu C (2023) A polynomial time algorithm for finding a minimum 4-partition of a submodular function. Proc. 34th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 1680–1691.Google Scholar
• [36] 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
• [37] Kapralov M, Krauthgamer R, Tardos J, Yoshida Y (2021) Toward tight bounds for spectral sparsification of hypergraphs. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 598–611.Google Scholar
• [38] Karger D (1993) Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proc. Fourth Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 21–30.Google Scholar
• [39] Karger D (2000) Minimum cuts in near-linear time. J. ACM 47(1):46–76.Crossref, Google Scholar
• [40] Karger D, Stein C (1996) A new approach to the minimum cut problem. J. ACM 43(4):601–640.Crossref, Google Scholar
• [41] Karlin A, Klein N, Gharan SO (2021) A (slightly) improved approximation algorithm for metric TSP. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 32–45.Google Scholar
• [42] Kawarabayashi K, Lin B (2020) A nearly 5/3-approximation FPT algorithm for min-k-cut. Proc. 31st ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 990–999.Google Scholar
• [43] Kawarabayashi K, Thorup M (2011) The minimum k-way cut of bounded size is fixed-parameter tractable. Proc. 52nd Annual Sympos. Foundations Comput. Sci. (ACM, New York), 160–169.Google Scholar
• [44] Kogan D, Krauthgamer R (2015) Sketching cuts in graphs and hypergraphs. Proc. 2015 Conf. Innovations Theoretical Comput. Sci. (ACM, New York), 367–376.Google Scholar
• [45] Lawler E (1973) Cutsets and partitions of hypergraphs. Networks 3(3):275–285.Crossref, Google Scholar
• [46] Li J, Panigrahi D (2020) Deterministic min-cut in poly-logarithmic max-flows. Proc. 61st Annual Sympos. Foundations Comput. Sci., 85–92.Google Scholar
• [47] Lokshtanov D, Saurabh S, Surianarayanan V (2020) A parameterized approximation scheme for Min k-Cut. Proc. 61st IEEE Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 798–809.Google Scholar
• [48] Manurangsi P (2017) Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. Proc. 49th Annual ACM Sympos. Theory Comput. (ACM, New York), 954–961.Google Scholar
• [49] 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):10.Crossref, Google Scholar
• [50] Nagamochi H, Nishimura K, Ibaraki T (1997) Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10(3):469–481.Crossref, Google Scholar
• [51] Nägele M, Sudakov B, Zenklusen R (2019) Submodular minimization under congruency constraints. Combinatorica 39:1351–1386.Crossref, Google Scholar
• [52] 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
• [53] Quanrud K (2019) Fast and deterministic approximations for k-cut. Proc. Approximation Randomization Combin. Optim. Algorithms Techniques, vol. 23 (Springer, New York), 1–20.Google Scholar
• [54] Queyranne M (1999) On optimum size-constrained set partitions. Presentation, Aussois Workshop on Combinatorial Optimization, Aussois, France.Google Scholar
• [55] Raghavendra P, Steurer D (2010) Graph expansion and the unique games conjecture. Proc. 42nd Annual ACM Sympos. Theory Comput. (ACM, New York), 755–764.Google Scholar
• [56] Ravi R, Sinha A (2008) Approximating k-cuts using network strength as a Lagrangean relaxation. Eur. J. Oper. Res. 186(1):77–90.Crossref, Google Scholar
• [57] Saran H, Vazirani V (1995) Finding k cuts within twice the optimal. SIAM J. Comput. 24(1):101–108.Crossref, Google Scholar
• [58] Soma T, Yoshida Y (2019) Spectral sparsification of hypergraphs. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 2570–2581.Google Scholar
• [59] Thorup M (2008) Minimum k-way cuts via deterministic greedy tree packing. Proc. 40th Annual ACM Sympos. Theory Comput. (ACM, New York), 159–166.Google Scholar
• [60] Xiao M (2008) An improved divide-and-conquer algorithm for finding all minimum k-way cuts. Proc. 19th Internat. Sympos. Algorithms Comput. (ACM, New York), 208–219.Google Scholar
• [61] Zenklusen R (2019) A 1.5-approximation for path TSP. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York-Philadelphia), 1539–1549.Google Scholar
• [62] Zhao L (2002) Approximation algorithms for partition and design problems in networks. Unpublished PhD thesis, Kyoto University, Kyoto, Japan.Google Scholar
• [63] Zhao L, Nagamochi H, Ibaraki T (2005) Greedy splitting algorithms for approximating multiway partition problems. Math. Programming 102(1):167–183.Crossref, Google Scholar