Studeny.a41

M. Studeny, J. Cussens, V. Kratochvil: The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture. International Journal of Approximate Reasoning 138 (2021), pp. 188-203.

Abstract
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.

AMS classification 68T30 52B12 90C10

Keywords: learning decomposable models; chordal graph polytope; clutter inequalities; dual polyhedron

A pdf version of a preprint (266kB) is available.
The paper builds on the following publications:

M. Studeny, J. Cussens: Towards using the chordal graph polytope in learning decomposable models. International Journal of Approximate Reasoning 88 (2017), pp. 259-281.
R. Hemmecke, S. Lindner, M. Studeny: Characteristic imsets for learning Bayesian network structure. International Journal of Approximate Reasoning 53 (2012), n. 9, pp. 1336-1349.
S. Lindner (2012) Discrete optimization in machine learning: learning Bayesian network structures and conditional independence implication. PhD thesis, TU Munich.

Note also that the paper is an extended version of a former conference proceedings paper:

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. 449-460.