Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in \(\widetilde{O}(mn^{2k-2})\) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k-cut problem, for k > 2.We give an algorithm that runs in \(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\) time for finding a minimum k-cut in hypergraphs of constant rank r. This algorithm betters the previous best running times for both the minimum cut and minimum k-cut problems for dense hypergraphs.Both of our algorithms are Monte Carlo, i.e., they return a minimum k-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/minimum-cut-and-minimum-k-cut-in-hypergraphs-via-branching-J4nlwOmV3w

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Association for Computing Machinery.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3570162
Publisher site
See Article on Publisher Site

Abstract

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in \(\widetilde{O}(mn^{2k-2})\) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k-cut problem, for k > 2.We give an algorithm that runs in \(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\) time for finding a minimum k-cut in hypergraphs of constant rank r. This algorithm betters the previous best running times for both the minimum cut and minimum k-cut problems for dense hypergraphs.Both of our algorithms are Monte Carlo, i.e., they return a minimum k-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Apr 15, 2023

Keywords: Hypergraph cut

References

  • Faster connectivity in low-rank hypergraphs via expander decomposition
    [,
  • Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k
    [,
  • Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k
    [,
  • Hypergraph k-cut for fixed k in deterministic polynomial time
    [,
  • Min-max partitioning of hypergraphs and symmetric submodular functions
    [,
  • Hypergraph k-Cut in randomized polynomial time
    [,
  • Isolating cuts, (Bi-)submodularity, and faster algorithms for connectivity
    [,
  • LP relaxation and tree packing for minimum k-cuts
    [,
  • Computing minimum cuts in hypergraphs
    [,
  • Minimum cut and minimum k-cut in hypergraphs via branching contractions
    [,
  • Computing minimum multiway cuts in hypergraphs
    [,
  • Random contractions and sampling for hypergraph and hedge connectivity
    [,
  • A polynomial algorithm for the k-cut problem for fixed k
    [,
  • Faster exact and approximate algorithms for k-Cut
    [,
  • The Karger-Stein algorithm is optimal for k-cut
    [,
  • A divide-and-conquer approach to the minimum k-way cut problem
    [,
  • A deterministic algorithm for finding all minimum k-way cuts
    [,
  • Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm
    [,
  • Minimum cuts in near-linear time
    [,
  • A new approach to the minimum cut problem
    [,
  • Recursive random contraction revisited
    [,
  • Deterministic global minimum cut of a simple graph in near-linear time
    [,
  • A Simple Hypergraph Min Cut Algorithm
    [,
  • Sketching cuts in graphs and hypergraphs
    [,
  • A fast hypergraph min-cut algorithm for circuit partitioning
    [,
  • Computing edge-connectivity in multigraphs and capacitated graphs
    [,
  • A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph
    [,
  • Minimizing symmetric submodular functions
    [,
  • A simple min-cut algorithm
    [,
  • Minimum K-way cuts via deterministic greedy tree packing
    [,
  • An improved divide-and-conquer algorithm for finding all minimum k-way cuts
    [,
  • Finding minimum 3-way cuts in hypergraphs
    [,