Repository logo
 

Characterizing Tightness of LP Relaxations by Forbidding Signed Minors

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Weller, Adrian 

Abstract

We consider binary pairwise graphical models and provide an exact characterization (necessary and sufficient conditions observing signs of potentials) of tightness for the LP relaxation on the triplet-consistent polytope of the MAP inference problem, by forbidding an odd-K5 (complete graph on 5 variables with all edges repulsive) as a signed minor in the signed suspension graph. This captures signs of both singleton and edge potentials in a compact and efficiently testable condition, and improves significantly on earlier results. We provide other results on tightness of LP relaxations by forbidding minors, draw connections and suggest paths for future research.

Description

Keywords

Journal Title

Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence

Conference Name

Journal ISSN

Volume Title

Publisher

Association for Uncertainty in Artificial Intelligence