0545447 20240103230145.520210912235959.9 85114479243 000704053400012 10.1016/j.ijar.2021.07.014 16 s. E cav_un_epca*02567740888-613X1381 (2021)188-203Elsevier learning decomposable models chordal graph polytope clutter inequalities dual polyhedron cav_un_auth*0101202 Studený Milan UTIA-B Matematická teorie rozhodování Department of Decision Making Theory MTR MTR Department of Decision Making Theory K Ú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-0545447.pdf https://www.sciencedirect.com/science/article/pii/S0888613X21001316?via%3Dihub GA19-04579S GA ČR CZ cav_un_auth*0380558 The integer linear programming approach to structural learning of decomposable graphical models led us earlier to the concept of a chordal graph polytope. An open mathematical question motivated by this research is what is the minimal set of linear inequalities defining this polytope, i.e. what are its facet-defining inequalities, and we came up in 2016 with a specific conjecture that it is the collection of so-called clutter inequalities. In this theoretical paper we give an implicit characterization of the minimal set of inequalities. Specifically, we introduce a dual polyhedron (to the chordal graph polytope) defined by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs. Our main result is that the vertices of this polyhedron yield the facet-defining inequalities for the chordal graph polytope. We also show that the original conjecture is equivalent to the condition that all vertices of the dual polyhedron are zero-one vectors. Using that result we disprove the original conjecture: we find a vector in the dual polyhedron which is not in the convex hull of zero-one vectors from the dual polyhedron. WOS BA 10000 10100 10101 2022 3 PR RVO:67985556 http://hdl.handle.net/11104/0322204 S 3+4 Article Computer Science Artificial Intelligence C COMPUTERSCIENCE.ARTIFICIALINTELLIGENCE 3.544 0.81 7.1 0.00478 0.721 5461 116 1.066 43.94 4.11 1708 Q1 3.794 142 Q2 61.7 Q3 Q2 0.83 Q2 61.724 2021 85114479243 SCOPUS PUBMED 000704053400012 WOS cav_un_epca*0256774 International Journal of Approximate Reasoning 0888-613X 1873-4731 Roč. 138 č. 1 2021 188 203 Elsevier