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 $G = (V, E 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 \tbinom\V\\2\ 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 F\$ whose vertices are precisely the characteristic vectors of multicuts of $G$ lifted from $G$, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.
%0 Journal Article
%1 Andres2022-si
%A Andres, Bjoern
%A Di Gregorio, Silvia
%A Irmai, Jannik
%A Lange, Jan-Hendrik
%D 2022
%I arXiv
%K
%T A polyhedral study of lifted multicuts
%X 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 $G = (V, E 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 \tbinom\V\\2\ 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 F\$ whose vertices are precisely the characteristic vectors of multicuts of $G$ lifted from $G$, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.
@article{Andres2022-si,
abstract = {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.},
added-at = {2024-09-10T11:56:37.000+0200},
author = {Andres, Bjoern and Di Gregorio, Silvia and Irmai, Jannik and Lange, Jan-Hendrik},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2c10321ace317a29cb373a577d9ece0a8/scadsfct},
interhash = {a9f2c70db704c2fc7535d2b64ff31cbe},
intrahash = {c10321ace317a29cb373a577d9ece0a8},
keywords = {},
publisher = {arXiv},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {A polyhedral study of lifted multicuts},
year = 2022
}
