Multiway cut

Let H=(V,E) be a connected hypergraph, and let [math]T \subseteq V[/math] be a set of terminals. A multiway cut with respect to T is a subset [math]F \subseteq E[/math] of hyperedges such that the terminals are in different components of the hypergraph [math]H'=(V, E\setminus F)[/math].

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 [math]k \geq 2[/math] an integer. A k-way cut of H is a subset [math]F \subseteq E[/math] of hyperedges such that the hypergraph [math]H'=(V,E\setminus F)[/math] has at least k components.

Let [math]c: E \to {\mathbb R}_+[/math] be a capacity function on the hyperedges. A mimimum k-way cut is a k-way cut F for which [math]\sum_{e\in F}c(e)[/math] is minimal.

Submodular generalization

Given a submodular function b on ground set V and a subset [math]\{t_1\dots,t_k\} \subseteq V[/math] of terminals, the submodular multiway partition problem is to find a partition [math]V_1, \dots,V_k[/math] such that [math]t_i \in V_i[/math] and [math]\sum b(V_i)[/math] 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 [math]V_i[/math] are required to be non-empty.