Characterizing Tightness of LP Relaxations by Forbidding Signed Minors

Adrian Weller
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:8-17, 2016.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-weller16a, title = {Characterizing Tightness of {LP} Relaxations by Forbidding Signed Minors}, author = {Weller, Adrian}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {8--17}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/weller16a/weller16a.pdf}, url = {https://proceedings.mlr.press/r14/weller16a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Characterizing Tightness of LP Relaxations by Forbidding Signed Minors %A Adrian Weller %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-weller16a %I PMLR %P 8--17 %U https://proceedings.mlr.press/r14/weller16a.html %V R14 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Weller, A.. (2016). Characterizing Tightness of LP Relaxations by Forbidding Signed Minors. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:8-17 Available from https://proceedings.mlr.press/r14/weller16a.html. Reissued by PMLR on 04 October 2026.

Related Material