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.

Submodular generalization

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.