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
%J Discrete Optimization
%K from:scadsfct topic_visualcomputing
%P 100757
%R 10.1016/j.disopt.2022.100757
%T A polyhedral study of lifted multicuts
%V 47
%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-11-29T12:17:17.000+0100},
author = {Andres, Bjoern and Di Gregorio, Silvia and Irmai, Jannik and Lange, Jan-Hendrik},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/227ff01c6e165027d3f8c58ba618e57b4/scads.ai},
doi = {10.1016/j.disopt.2022.100757},
interhash = {a9f2c70db704c2fc7535d2b64ff31cbe},
intrahash = {27ff01c6e165027d3f8c58ba618e57b4},
journal = {Discrete Optimization},
keywords = {from:scadsfct topic_visualcomputing},
pages = 100757,
publisher = {arXiv},
timestamp = {2024-11-29T12:17:17.000+0100},
title = {A polyhedral study of lifted multicuts},
volume = 47,
year = 2022
}
