Dual Formulation of the Chordal Graph Conjecture

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

Dual Formulation of the Chordal Graph Conjecture

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

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

1 Citation (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings of Machine Learning Research
Subtitle of host publication	Proceedings of the 10th International Conference on Probabilistic Graphical Models
Editors	Manfred Jaeger, Thomas D. Nielsen
Pages	449-460
Number of pages	12
Volume	138
Publication status	Published - 25 Sept 2020
Event	10th International Conference on Probabilistic Graphical Models - Hotel Comwell Rebild Bakker, Skørping, Denmark Duration: 23 Sept 2020 → 25 Sept 2020 https://pgm2020.cs.aau.dk/

Publication series

Name	Proceedings of Machine Learning Research
Volume	138
ISSN (Electronic)	2640-3498

Conference

Conference	10th International Conference on Probabilistic Graphical Models
Abbreviated title	PGM 2020
Country/Territory	Denmark
City	Skørping
Period	23/09/20 → 25/09/20
Internet address	https://pgm2020.cs.aau.dk/

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.

Handle.net

Persistent link

Cite this

@inproceedings{cfe07eb8ef06439d8fc11bd2d40ed8c8,

title = "Dual Formulation of the Chordal Graph Conjecture",

abstract = "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.",

author = "Milan Studen{\'y} and James Cussens and V{\'a}clav Kratochv{\'i}l",

note = "Funding Information: The research of Milan Studen{\'y} and V{\'a}clav Kratochv{\'i}l has been supported by the grant GA{\v C}R number 19-04579S.; 10th International Conference on Probabilistic Graphical Models, PGM 2020 ; Conference date: 23-09-2020 Through 25-09-2020",

year = "2020",

month = sep,

day = "25",

language = "English",

volume = "138",

series = "Proceedings of Machine Learning Research",

pages = "449--460",

editor = "Manfred Jaeger and Nielsen, \{Thomas D.\}",

booktitle = "Proceedings of Machine Learning Research",

url = "https://pgm2020.cs.aau.dk/",

}

Studený, M, Cussens, J & Kratochvíl, V 2020, Dual Formulation of the Chordal Graph Conjecture. in M Jaeger & TD Nielsen (eds), Proceedings of Machine Learning Research: Proceedings of the 10th International Conference on Probabilistic Graphical Models. vol. 138, Proceedings of Machine Learning Research, vol. 138, pp. 449-460, 10th International Conference on Probabilistic Graphical Models, Skørping, Denmark, 23/09/20.

Dual Formulation of the Chordal Graph Conjecture. / Studený, Milan; Cussens, James; Kratochvíl, Václav.
Proceedings of Machine Learning Research: Proceedings of the 10th International Conference on Probabilistic Graphical Models. ed. / Manfred Jaeger; Thomas D. Nielsen. Vol. 138 2020. p. 449-460 (Proceedings of Machine Learning Research; Vol. 138).

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

TY - GEN

T1 - Dual Formulation of the Chordal Graph Conjecture

AU - Studený, Milan

AU - Cussens, James

AU - Kratochvíl, Václav

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

PY - 2020/9/25

Y1 - 2020/9/25

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

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

UR - http://proceedings.mlr.press/v138/studeny20a.html

M3 - Conference Contribution (Conference Proceeding)

VL - 138

T3 - Proceedings of Machine Learning Research

SP - 449

EP - 460

BT - Proceedings of Machine Learning Research

A2 - Jaeger, Manfred

A2 - Nielsen, Thomas D.

T2 - 10th International Conference on Probabilistic Graphical Models

Y2 - 23 September 2020 through 25 September 2020

ER -

Dual Formulation of the Chordal Graph Conjecture

Abstract

Publication series

Conference

Bibliographical note

Handle.net

Other files and links

Fingerprint

Cite this