  The minimum $s$-$t$ 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 $s$-$t$ cut problem can be
reduced to a tractable graph $s$-$t$ 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.
