# Multiway cut

Let H=(V,E) be a connected hypergraph, and let $T \subseteq V$ be a set of terminals. A multiway cut with respect to T is a subset $F \subseteq E$ of hyperedges such that the terminals are in different components of the hypergraph $H'=(V, E\setminus F)$.
A similar notion can be defined if no terminals are given (in some papers, this is also referred to as multiway cut). Let H=(V,E) be a connected hypergraph and $k \geq 2$ an integer. A k-way cut of H is a subset $F \subseteq E$ of hyperedges such that the hypergraph $H'=(V,E\setminus F)$ has at least k components.
Let $c: E \to {\mathbb R}_+$ be a capacity function on the hyperedges. A mimimum k-way cut is a k-way cut F for which $\sum_{e\in F}c(e)$ is minimal.
Given a submodular function b on ground set V and a subset $\{t_1\dots,t_k\} \subseteq V$ of terminals, the submodular multiway partition problem is to find a partition $V_1, \dots,V_k$ such that $t_i \in V_i$ and $\sum b(V_i)$ is minimized. The minimum multiway cut problem for graphs is a special case, where b is the cut function. The minimum multiway cut problem in hypergraphs can also be reduced to this problem.
One can define the submodular k-way partition problem analogously: there are no given terminals, and the sets $V_i$ are required to be non-empty.