Research map / Learning theory and algorithms / Combinatorial and search optimization
Box Facets and Cut Facets of Lifted Multicut Polytopes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes which lower box inequalities define facets of lifted multicut polytopes via an efficiently decidable graph condition (using Menger's theorem), and proves that deciding whether a cut inequality defines a facet is NP-hard.
Problem
Facet-defining inequalities of lifted multicut polytopes: which lower box inequalities and which cut inequalities define facets, needed for LP-based exact algorithms for the lifted multicut problem.
Approach
Gives a necessary and sufficient, efficiently decidable graph-theoretic condition (no simple paths/cycles in the augmented graph consisting of uw-separators with cut-node endpoints) for lower box inequalities to be facets, and reduces 3-SAT to show facet-definingness of cut inequalities is NP-hard via f_d-paths.
Key results
- Lower box inequality 0 <= x_uw is facet-defining iff two efficiently checkable graph conditions hold (no violating simple path and no violating simple cycle in the augmented graph of uw-separators).
- Deciding whether a cut inequality defines a facet of the lifted multicut polytope is NP-hard, even when |F| = 1, via reduction from 3-SAT.
- Lemma: any simple cycle of uw-separators avoiding cut-nodes has even length, via Menger's theorem applied to an auxiliary graph.
Surprising findings
- Facet-definingness of cut inequalities is NP-hard to decide even in the special case of a single augmented edge (|F| = 1).
Limitations
- Does not provide a characterization of cut-inequality facets beyond the NP-hard special case.
- No computational experiments or implementation of the facet test.
Experimental setup
Builds on: lifted multicut polytope (Horňáková et al.) Menger's theorem 3-SAT NP-hardness
Closest papers by meaning
- A Message Passing Algorithm for the Minimum Cost Multicut Problem (CVPR 2017 · similarity 0.87)
- Analysis and Optimization of Graph Decompositions by Lifted Multicuts (ICML 2017 · similarity 0.86)
- Convexity Shape Constraints for Image Segmentation (CVPR 2016 · similarity 0.84)
- Learning convex polytopes with margin (NeurIPS 2018 · similarity 0.84)
- PolyhedronNet: Representation Learning for Polyhedra with Surface-attributed Graph (ICLR 2025 · similarity 0.82)
- New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results (NeurIPS 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.