# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Lifting of Multicuts

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

1503.03791v5.pdf

(Preprint), 448KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Andres, B., Fuksova, A., & Lange, J.-H. (2016). Lifting of Multicuts. Retrieved from http://arxiv.org/abs/1503.03791.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0028-DCA9-7

##### Abstract

For every simple, undirected graph $G = (V, E)$, a one-to-one relation exists
between the decompositions and the multicuts of $G$. A decomposition of $G$ is
a partition $\Pi$ of $V$ such that, for every $U \in \Pi$, the subgraph of $G$
induced by $U$ is connected. A multicut of $G$ is an $M \subseteq E$ such that,
for every (chordless) cycle $C \subseteq E$ of $G$, $|M \cap C| \neq 1$. The
multicut related to a decomposition is the set of edges that straddle distinct
components. The characteristic function $x \in \{0, 1\}^E$ of a multicut $M =
x^{-1}(1)$ of $G$ makes explicit, for every pair $\{v,w\} \in E$ of neighboring
nodes, whether $v$ and $w$ are in distinct components. In order to make
explicit also for non-neighboring nodes, specifically, for all $\{v,w\} \in E'$
with $E \subseteq E' \subseteq {V \choose 2}$, whether $v$ and $w$ are in
distinct components, we define a lifting of the multicuts of $G$ to multicuts
of $G' = (V, E')$. We show that, if $G$ is connected, the convex hull of the
characteristic functions of those multicuts of $G'$ that are lifted from $G$ is
an $|E'|$-dimensional polytope in $\mathbb{R}^{E'}$. We establish properties of
trivial facets of this polytope.