A polyhedral study of lifted multicuts
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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 Ĝ=(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 [Formula presented] of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in RE∪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.
Details
Original language | English |
---|---|
Article number | 100757 |
Journal | Discrete optimization |
Volume | 47 |
Publication status | Published - Feb 2023 |
Peer-reviewed | Yes |
External IDs
ORCID | /0000-0001-5036-9162/work/161888484 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- Graph decomposition, Multicut, Multicut polytope