# 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.