Dual formulation of the chordal graph conjecture

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F21%3A00539983" target="_blank" >RIV/67985556:_____/21:00539983 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Dual formulation of the chordal graph conjecture

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Dual formulation of the chordal graph conjecture

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10103 - Statistics and probability

Projekt

<a href="/cs/project/GA19-04579S" target="_blank" >GA19-04579S: Struktury podmíněné nezávislosti: metody polyedrální geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of Machine Learning Research, Volume 138: International Conference on Probabilistic Graphical Models, 23-25 September 2020, Hotel Comwell Rebild Bakker, Skørping, Denmark

ISBN

—

ISSN

2640-3498

e-ISSN

2640-3498

Počet stran výsledku

12

Strana od-do

449-460

Název nakladatele

JMLR, Inc. and Microtome Publishing

Místo vydání

Brookline

Místo konání akce

Skørping

Datum konání akce

23. 9. 2020

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—