A Polyhedral Study of Lifted Multicuts
  Fundamental to many applications in data analysis are the decompositions of a
graph, i.e. partitions of the node set into component-inducing subsets. One way
of encoding decompositions is by multicuts, the subsets of those edges that
straddle distinct components. Recently, a lifting of multicuts from a graph $G
= (V, E)$ to an augmented graph $\hat G = (V, E \cup F)$ has been proposed in
the field of image analysis, with the goal of obtaining a more expressive
characterization of graph decompositions in which it is made explicit also for
pairs $F \subseteq \tbinom{V}{2} \setminus E$ of non-neighboring nodes whether
these are in the same or distinct components. In this work, we study in detail
the polytope in $\mathbb{R}^{E \cup F}$ whose vertices are precisely the
characteristic vectors of multicuts of $\hat G$ lifted from $G$, connecting it,
in particular, to the rich body of prior work on the clique partitioning and
multilinear polytope.
