We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2^O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.
Extension complexity of the correlation polytope / Aboulker, P.; Fiorini, S.; Huynh, T.; Macchia, M.; Seif, J.. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - (2018).
Extension complexity of the correlation polytope
Huynh, T.;
2018
Abstract
We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2^O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
