0539983 20250123091652.620210222235959.9 85114463462 001231262100039 12 s. E cav_un_epca*0542414Proceedings of Machine Learning Research, Volume 138: International Conference on Probabilistic Graphical Models, 23-25 September 2020, Hotel Comwell Rebild Bakker, Skørping, Denmark449-460BrooklineJMLR, Inc. and Microtome Publishing2021NielsenT. D.JaegerM. Learning decomposable models chordal graph polytope clutter inequalities dual polyhedron chordal graph inequalities cav_un_auth*0101202 Studený Milan UTIA-B Matematická teorie rozhodování Department of Decision Making Theory MTR MTR Department of Decision Making Theory Ústav teorie informace a automatizace AV ČR, v. v. i. cav_un_auth*0332730 Cussens J. GB cav_un_auth*0216188 Kratochvíl Václav UTIA-B Matematická teorie rozhodování Department of Decision Making Theory MTR MTR CZ Ústav teorie informace a automatizace AV ČR, v. v. i. http://library.utia.cas.cz/separaty/2021/MTR/studeny-0539983.pdf GA19-04579S GA ČR CZ cav_un_auth*0380558 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. cav_un_auth*0406024 International Conference on Probabilistic Graphical Models 2021 /10./ 20200923 20200925 Skørping DK BA 10000 10100 10103 2022 3 PR RVO:67985556 http://hdl.handle.net/11104/0320770 S 2021 85114463462 SCOPUS PUBMED 001231262100039 WOS cav_un_epca*0542414 Proceedings of Machine Learning Research, Volume 138: International Conference on Probabilistic Graphical Models, 23-25 September 2020, Hotel Comwell Rebild Bakker, Skørping, Denmark JMLR, Inc. and Microtome Publishing 2021 Brookline 449 460 2640-3498 Nielsen T. D. 340 Jaeger M. 340