A Polyhedral Study of Lifted Multicuts
share
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 Ĝ = (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 ⊆V2∖ E of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in ℝ^E ∪ F whose vertices are precisely the characteristic vectors of multicuts of Ĝ lifted from G, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.
READ FULL TEXT