Hypergraph Cuts with General Splitting Functions
From MaRDI portal
Publication:5094916
Abstract: The minimum - cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multi-way relationships, and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a "cut hyperedge" is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph - cut problem can be reduced to a tractable graph - cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. We also analyze extensions to multiway cuts with at least three terminal nodes and identify a natural class of splitting functions for which the problem can be reduced in an approximation-preserving way to the node-weighted multiway cut problem in graphs, again subject to a submodularity property. Finally, we outline several open questions on general hypergraph cut problems.
Recommendations
- On the relative strength of different generalizations of split cuts
- Cutting hyperplanes for divide-and-conquer
- Sketching cuts in graphs and hypergraphs
- Cut vertex transit functions of hypergraphs
- Cutwidth of split graphs and threshold graphs
- Algorithms for the determination of cutsets in a hypergraph
- A Cheeger cut for uniform hypergraphs
- Realization of set functions as cut functions of graphs and hypergraphs
- Cutsets in bipartite graphs*
- Minimum cuts and sparsification in hypergraphs
Cites work
- k-way hypergraph partitioning via n-level recursive bisection
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A faster strongly polynomial time algorithm for submodular function minimization
- A Gomory-Hu cut tree representation of a netlist partitioning problem
- An algorithm for improving graph partitions
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
- Approximation techniques for hypergraph partitioning problems
- Cross-linked structure of network evolution
- Cutsets and partitions of hypergraphs
- Diffuse interface models on graphs for classification of high dimensional data
- Emerging frontiers in nonlinear science
- Flow-based algorithms for local graph clustering
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 6850403 (Why is no real title available?)
- scientific article; zbMATH DE number 7051294 (Why is no real title available?)
- scientific article; zbMATH DE number 742960 (Why is no real title available?)
- scientific article; zbMATH DE number 1849127 (Why is no real title available?)
- scientific article; zbMATH DE number 3225808 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication
- Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
- Integer Programming and Combinatorial Optimization
- Max flows in O(nm) time, or better
- Minimizing a sum of submodular functions
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Minimum cuts, modular functions, and matroid polyhedra
- Modeling hypergraphs by graphs with the same mincut properties
- Multiway cuts in directed and node weighted graphs
- Network Flow and Testing Graph Connectivity
- Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
- Networks, crowds and markets. Reasoning about a highly connected world.
- On two-dimensional sparse matrix partitioning: models, methods, and a recipe
- Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
- Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
- Realization of set functions as cut functions of graphs and hypergraphs
- Realizing symmetric set functions as hypergraph cut capacity
- Recent directions in netlist partitioning: a survey
- Revisiting Hypergraph Models for Sparse Matrix Partitioning
- Simple and fast rounding algorithms for directed and node-weighted multiway cut
- Simultaneous input and output matrix partitioning for outer-product -- parallel sparse matrix-matrix multiplication
- Statistical mechanics of complex networks
- The complexity of satisfiability problems
- The ellipsoid method and its consequences in combinatorial optimization
- The expressive power of binary submodular functions
- The Structure and Function of Complex Networks
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Three hypergraph eigenvector centralities
Cited in
(15)- A generalized \(\alpha\)-cut
- Split closure and intersection cuts
- Partial hyperplane activation for generalized intersection cuts
- scientific article; zbMATH DE number 637334 (Why is no real title available?)
- scientific article; zbMATH DE number 2086918 (Why is no real title available?)
- Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
- Core-Periphery Detection in Hypergraphs
- What Are Higher-Order Networks?
- Comparing the principal eigenvector of a hypergraph and its shadows
- Hypergraph analysis based on a compatible tensor product structure
- Splitting-off in hypergraphs
- Cut sparsification and succinct representation of submodular hypergraphs
- Splitting-off in hypergraphs
- Hypergraph connectivity augmentation in strongly polynomial time
- Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
This page was built for publication: Hypergraph Cuts with General Splitting Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5094916)
