On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

Research output: Working paperOther research output

Abstract

We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph G depending linearly on the size of G and involving the depth of a decomposition tree of G in terms of basic perfect graphs.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages17
Publication statusPublished - 20 Jun 2017

Publication series

NamearXiv
Volume1706.05496

Fingerprint

Linear Extension
Perfect Graphs
Stable Set
Polytopes
Stable Set Polytope
Tree Decomposition
Graph in graph theory
Skew
Join
Linearly
Non-negative
Partition
Decompose

Cite this

Hu, H., & Laurent, M. (2017). On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs. (arXiv; Vol. 1706.05496). Ithaca: Cornell University Library.
@techreport{8d5888cec7884b10b10012b8b55c590d,
title = "On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs",
abstract = "We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph G depending linearly on the size of G and involving the depth of a decomposition tree of G in terms of basic perfect graphs.",
author = "Hao Hu and Monique Laurent",
year = "2017",
month = "6",
day = "20",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

Hu, H & Laurent, M 2017 'On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs' arXiv, vol. 1706.05496, Cornell University Library, Ithaca.

On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs. / Hu, Hao; Laurent, Monique.

Ithaca : Cornell University Library, 2017. (arXiv; Vol. 1706.05496).

Research output: Working paperOther research output

TY - UNPB

T1 - On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

AU - Hu, Hao

AU - Laurent, Monique

PY - 2017/6/20

Y1 - 2017/6/20

N2 - We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph G depending linearly on the size of G and involving the depth of a decomposition tree of G in terms of basic perfect graphs.

AB - We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph G depending linearly on the size of G and involving the depth of a decomposition tree of G in terms of basic perfect graphs.

M3 - Working paper

T3 - arXiv

BT - On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

PB - Cornell University Library

CY - Ithaca

ER -