Dual Formulation of the Chordal Graph Conjecture

Milan Studený, James Cussens, Václav Kratochvíl

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

1 Citation (Scopus)


The idea of an integer linear programming approach to structural learning of decomposable graphical models led to the study of the so-called 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 so-called 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) facet-defining inequalities of the chordal graph polytope. The original conjecture is then equivalent to a statement that all vertices of the dual polyhedron are zero-one vectors. This dual formulation of the conjecture offers a more intuitive view on the problem and allows us to disprove the conjecture.
Original languageEnglish
Title of host publicationProceedings of Machine Learning Research
Subtitle of host publicationProceedings of the 10th International Conference on Probabilistic Graphical Models
EditorsManfred Jaeger, Thomas D. Nielsen
Number of pages12
Publication statusPublished - 25 Sept 2020
Event10th International Conference on Probabilistic Graphical Models - Hotel Comwell Rebild Bakker, Skørping, Denmark
Duration: 23 Sept 202025 Sept 2020

Publication series

NameProceedings of Machine Learning Research
ISSN (Electronic)2640-3498


Conference10th International Conference on Probabilistic Graphical Models
Abbreviated titlePGM 2020
Internet address

Bibliographical note

Funding Information:
The research of Milan Studený and Václav Kratochvíl has been supported by the grant GAČR number 19-04579S.


Dive into the research topics of 'Dual Formulation of the Chordal Graph Conjecture'. Together they form a unique fingerprint.

Cite this