Document Open Access Logo

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

Authors Calvin Beideman , Karthekeyan Chandrasekaran , Weihang Wang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.16.pdf
  • Filesize: 0.88 MB
  • 18 pages

Document Identifiers

Author Details

Calvin Beideman
  • University of Illinois Urbana-Champaign, IL, USA
Karthekeyan Chandrasekaran
  • University of Illinois Urbana-Champaign, IL, USA
Weihang Wang
  • University of Illinois Urbana-Champaign, IL, USA

Funding

  • Beideman, Calvin: Supported in part by NSF grants CCF-1814613 and CCF-1907937.
  • Chandrasekaran, Karthekeyan: Supported in part by NSF grants CCF-1814613 and CCF-1907937.
  • Wang, Weihang: Supported in part by NSF grants CCF-1814613 and CCF-1907937.

Cite AsGet BibTex

Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang. Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.16

Abstract

We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems - namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph G = (V, E) with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k non-empty parts (V₁, V₂, …, V_k) - known as a k-partition - so as to minimize an objective of interest. 1) If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. 2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an n^{O(k)}p-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known n^{O(k²)}p-time deterministic algorithm, where n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • hypergraphs
  • k-partitioning
  • counting
  • enumeration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. Abboud, R. Krauthgamer, and O. Trabelsi. Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1725-1737, 2021. Google Scholar
  2. K. Ahn and S. Guha. Graph sparsification in the semi-streaming model. In Proceeings of the 36th International Colloquium on Automata, Languages and Programming: Part II, ICALP, pages 328-338, 2009. Google Scholar
  3. K. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 459-467, 2012. Google Scholar
  4. K. Ahn, S. Guha, and A. McGregor. Graph sketches: Sparsification, spanners, and subgraphs. In Proceedings of the 31st Symposium on Principles of Database Systems, PODS, pages 5-14, 2012. Google Scholar
  5. D. Applegate, R. Bixby, V. Chvátal, and W. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006. Google Scholar
  6. N. Bansal, O. Svensson, and L. Trevisan. New notions and constructions of sparsification for graphs and hypergraphs. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 910-928, 2019. Google Scholar
  7. C. Beideman, K. Chandrasekaran, and W. Wang. Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k, 2022. URL: http://arxiv.org/abs/2204.09178.
  8. C. Beideman, K. Chandrasekaran, and W. Wang. Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2022. Google Scholar
  9. A. Benczur. A representation of cuts within 6/5 times the edge connectivity with applications. In Proceedings of the 36th Annual IEEE Foundations of Computer Science, FOCS, pages 92-102, 1995. Google Scholar
  10. A. Benczur. Cut structures and randomized algorithms in edge-connectivity problems. PhD thesis, MIT, 1997. Google Scholar
  11. A. Benczur and M. Goemans. Deformable polygon representation and near-mincuts. Building Bridges: Between Mathematics and Computer Science, M. Groetschel and G.O.H. Katona, Eds., Bolyai Society Mathematical Studies, 19:103-135, 2008. Google Scholar
  12. K. Chandrasekaran and C. Chekuri. Hypergraph k-cut for fixed k in deterministic polynomial time. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science, FOCS, pages 810-821, 2020. Google Scholar
  13. K. Chandrasekaran and C. Chekuri. Min-max partitioning of hypergraphs and symmetric submodular functions. In Proceedings of the 32nd annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1026-1038, 2021. Google Scholar
  14. K. Chandrasekaran and W. Wang. Fixed Parameter Approximation Scheme for Min-max k-cut. In Integer Programming and Combinatorial Optimization, IPCO, pages 354-367, 2021. Google Scholar
  15. K. Chandrasekaran, C. Xu, and X. Yu. Hypergraph k-cut in randomized polynomial time. Mathematical Programming (Preliminary version in SODA 2018), 186:85-113, 2019. Google Scholar
  16. C. Chekuri, K. Quanrud, and C. Xu. LP relaxation and tree packing for minimum k-cut. SIAM Journal on Discrete Mathematics, 34(2):1334-1353, 2020. Google Scholar
  17. C. Chekuri and C. Xu. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47(6):2118-2156, 2018. Google Scholar
  18. Y. Chen, S. Khanna, and A. Nagda. Near-linear size hypergraph cut sparsifiers. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 61-72, 2020. Google Scholar
  19. W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver. Combinatorial Optimization. Wiley, 1997. Google Scholar
  20. K. Fox, D. Panigrahi, and F. Zhang. Minimum cut and minimum k-cut in hypergraphs via branching contractions. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 881-896, 2019. Google Scholar
  21. M. Ghaffari, D. Karger, and D. Panigrahi. Random contractions and sampling for hypergraph and hedge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1101-1114, 2017. Google Scholar
  22. M. X. Goemans and V. S. Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15:499-513, 1995. Google Scholar
  23. O. Goldschmidt and D. Hochbaum. A Polynomial Algorithm for the k-cut Problem for Fixed k. Mathematics of Operations Research (Preliminary version in FOCS 1988), 19(1):24-37, February 1994. Google Scholar
  24. F. Guinez and M. Queyranne. The size-constrained submodular k-partition problem. Unpublished manuscript. Available at https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1. See also https://smartech.gatech.edu/bitstream/handle/1853/43309/Queyranne.pdf, 2012.
  25. A. Gupta, D. Harris, E. Lee, and J. Li. Optimal Bounds for the k-cut Problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.08301.
  26. A. Gupta, E. Lee, and J. Li. The number of minimum k-cuts: improving the Karger-Stein bound. In Proceedings of the 51st ACM Symposium on Theory of Computing, STOC, pages 229-240, 2019. Google Scholar
  27. A. Gupta, E. Lee, and J. Li. The Karger-Stein algorithm is optimal for k-cut. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC, pages 473-484, 2020. Google Scholar
  28. M. Kapralov, R. Krauthgamer, J. Tardos, and Y. Yoshida. Towards tight bounds for spectral sparsification of hypergraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 598-611, 2021. Google Scholar
  29. D. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, 2000. Google Scholar
  30. D. Karger and C. Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, July 1996. Google Scholar
  31. A. Karlin, N. Klein, and S-O. Gharan. A (slightly) improved approximation algorithm for metric tsp. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 32-45, 2021. Google Scholar
  32. D. Kogan and R. Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15, pages 367-376, 2015. Google Scholar
  33. E. Lawler. Cutsets and Partitions of Hypergraphs. Networks, 3:275-285, 1973. Google Scholar
  34. J. Li and D. Panigrahi. Deterministic Min-cut in Poly-logarithmic Max-flows. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science, FOCS, pages 85-92, 2020. Google Scholar
  35. M. Nägele, B. Sudakov, and R. Zenklusen. Submodular minimization under congruency constraints. Combinatorica, 39:1351-1386, 2019. Google Scholar
  36. K. Okumoto, T. Fukunaga, and H. Nagamochi. Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica, 62(3):787-806, 2012. Google Scholar
  37. M. Queyranne. On optimum size-constrained set partitions, 1999. Talk at Aussiois workshop on Combinatorial Optimization. Google Scholar
  38. T. Soma and Y. Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2570-2581, 2019. Google Scholar
  39. M. Thorup. Minimum k-way Cuts via Deterministic Greedy Tree Packing. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC, pages 159-166, 2008. Google Scholar
  40. R. Zenklusen. A 1.5-Approximation for Path TSP. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1539-1549, 2019. Google Scholar
  41. L. Zhao. Approximation algorithms for partition and design problems in networks. PhD thesis, Graduate School of Informatics, Kyoto University, Japan, 2002. Google Scholar
  42. L. Zhao, H. Nagamochi, and T. Ibaraki. Greedy splitting algorithms for approximating multiway partition problems. Mathematical Programming, 102(1):167-183, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact