A polyhedral study of lifted multicuts

Research output: Contribution to journalResearch articleContributedpeer-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 languageEnglish
Article number100757
JournalDiscrete optimization
Volume47
Publication statusPublished - Feb 2023
Peer-reviewedYes

External IDs

ORCID /0000-0001-5036-9162/work/161888484

Keywords

Keywords

  • Graph decomposition, Multicut, Multicut polytope