Planar Cycle Covering Graphs

Julian Yarkony, Alexander T. Ihler, Charless C. Fowlkes
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:839-847, 2011.

Abstract

We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-yarkony11a, title = {Planar Cycle Covering Graphs}, author = {Yarkony, Julian and Ihler, Alexander T. and Fowlkes, Charless C.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {839--847}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/yarkony11a/yarkony11a.pdf}, url = {https://proceedings.mlr.press/r9/yarkony11a.html}, abstract = {We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Planar Cycle Covering Graphs %A Julian Yarkony %A Alexander T. Ihler %A Charless C. Fowlkes %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-yarkony11a %I PMLR %P 839--847 %U https://proceedings.mlr.press/r9/yarkony11a.html %V R9 %X We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound. %Z Reissued by PMLR on 04 October 2026.
APA
Yarkony, J., Ihler, A.T. & Fowlkes, C.C.. (2011). Planar Cycle Covering Graphs. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:839-847 Available from https://proceedings.mlr.press/r9/yarkony11a.html. Reissued by PMLR on 04 October 2026.

Related Material