On the stable set polytope of a series-parallel graph (Q1106858): Difference between revisions

Let \(G=(V,E)\) be a graph. A stable (independent) set in \(G\) is a set of nodes, no two of which are adjacent. Given a stable set \(S\) of \(G\), the incidence vector of \(S\), \(x^ s\) is the 0-1 vector such that \(x^ s(u)=1\) if \(u\in S\) and \(x^ s(u)=0\) if not. The stable set polytope of \(G\), denoted by \(P(G)\), is the convex hull of the incidence vectors of all the stable sets of \(G\). If \(G=(V,E)\) is a graph, then each incidence vector of a stable set of \(G\) satisfies the inequalities \[ \begin{cases} 0\leq x(u)\leq 1 \quad&\text{for all }u\in V, \\ x(u) + x(v)\leq 1 \quad&\text{for all }uv\in E, \\ \sum_{u\in C} x(u) \leq \frac{| C| -1}{2} \quad&\text{for all induced cycles \(C\) of \(G\) such that \(| C|\) is odd.} \end{cases} \tag{1} \] In 1975, Chvatal conjectured that (1) defines the polytope \(P(G)\) when \(G\) is series-parallel. This conjecture has been proved by J. P. Uhry and Boulala in 1979 using LP-duality, and independently by Clamcy in 1977. In this note we give a short proof of Chvatal's conjecture. Given a graph \(G=(V,E)\), if \(ax \leq \alpha\) defines a facet of \(P(G)\) (i.e. a face of dimension \(| V| -1)\) and \(G_ a\) is the graph induced by it, we show that: (i) If \(G_ a\) contains a path \((v_0, v_1, \ldots, v_{p+1})\) whose intern al nodes \(v_1, \ldots, v_ p\) are of degree two, then \(a(v_1)= \ldots =a(v_ p)\). (ii) If \(u\), \(v\) are two nodes of \(G_ a\), then at most one path in \(G_ a\) wh ich joins \(u\) and \(v\) can have all internal nodes of degree two. (iii) \(G_ a\) does not contain a node of degree one. Using this, we prove that if \(G\) is a series-parallel graph, then any facet defining inequality of \(P(G)\) is of the forms described in (1).