M. Studeny, J. Cussens, V. Kratochvil:
Dual formulation of the chordal graph conjecture.
In Proceedings of Machine Learning Research
138 (2020), Proceedings of the International Conference on Probabilistic Graphical Models [PGM 2020],
(M. Jaeger, T. D. Nielsen eds.), pp. 449460.
 Abstract

The idea of an integer linear programming approach to structural learning of decomposable graphical models led to
the study of the socalled chordal graph polytope. An open mathematical question is what is the minimal set
of linear inequalities defining this polytope. Some time ago we came up with a specific conjecture that the polytope is
defined by socalled clutter inequalities.
In this theoretical paper we give a dual formulation of the conjecture. Specifically, we introduce a certain dual polyhedron defined
by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs.
The main result is that the list of (all) vertices of this bounded polyhedron gives rise to the list of (all) facetdefining inequalities
of the chordal graph polytope. The original conjecture is then equivalent to a statement that all vertices of the dual polyhedron
are zeroone vectors. This dual formulation of the conjecture offers a more intuitive view on the problem and allows us to disprove
the conjecture.
 AMS classification 52B12 68T30 90C27
 Keywords
 learning decomposable models
 chordal graph polytope
 clutter inequalities
 dual polyhedron
 chordal graph inequalities
A
pdf version (311kB) is available.
The contribution builds on the following papers: