Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

Abstract

Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC’17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of G.

1 Introduction

It is a classic result that integer programs with a totally unimodular constraint matrix A are solvable in strongly polynomial time. Very recently, Artmann, Weismantel and Zenklusen [1] generalized this to bimodular matrices A. These include all matrices with all subdeterminants in $\{-2,-1,0,1,2\}$. As noted in [1], this has consequences for the maximum weight stable set problem in graphs as follows.

Let ${\text {STAB}}(G)$ be the stable set polytope of a graph G and note that

$$\begin{aligned} {\text {STAB}}(G) = {\text {conv}}\{ x \in \{0,1\}^{V(G)} \mid Mx \leqslant \mathbf {1} \}, \end{aligned}$$

where $M \in \{0,1\}^{E(G) \times V(G)}$ is the edge-node incidence matrix of G. It is well-known that the maximum absolute value of a subdeterminant of M is equal to $2^{{\text {ocp}}(G)}$, where ${\text {ocp}}(G)$ is the maximum number of (node-)disjoint odd cycles of G (see [2]). Therefore, the bimodular algorithm of [1] can be used to efficiently compute a maximum weight stable set in a graph without two disjoint odd cycles.

Although the bimodular algorithm is extremely powerful, it provides limited insight on which properties of graphs with ${\text {ocp}}(G) \leqslant 1$ are relevant to derive efficient algorithms for graphs with higher odd cycle packing number. Indeed, in light of recent work linking the complexity and structural properties of integer programs to the magnitude of its subdeterminants [1, 3,4,5,6,7,8], it is tempting to believe that integer programs with bounded subdeterminants can be solved in polynomial time. This would imply in particular that the stable set problem on graphs with ${\text {ocp}}(G) \leqslant k$ is polynomial for every fixed k. Conforti, Fiorini, Huynh, Joret, and Weltge [9] recently proved this is true under the additional assumption that G has bounded (Euler) genus.¹

Furthermore, by itself the bimodular algorithm does not imply any linear description of the stable set polytope of graphs G with ${\text {ocp}}(G) = 1$. It turns out that for such graphs, ${\text {STAB}}(G)$ may have many facets with high coefficients that do not seem to allow a “nice” combinatorial description in the original space. While stable set polytopes have been studied for several classes of graphs, very little is known about ${\text {STAB}}(G)$ when ${\text {ocp}}(G) = 1$.

Our main result is to show that every such stable set polytope admits a compact description in an “extended” space. An extended formulation of a polyhedron P is a description of the form $P = \{ x \mid \exists y : Ax + By \leqslant b \}$ whose size is the number of inequalities in $Ax + By \leqslant b$. The extension complexity of P, denoted ${\text {xc}}(P)$, is the minimum size of an extended formulation of P. Our main result is the following.

Theorem 1

For every n-node graph G with ${\text {ocp}}(G) \leqslant 1$, ${\text {STAB}}(G)$ admits a size-$O(n^2)$ extended formulation. Moreover, this extended formulation can be constructed in polynomial time.

Note that this does not follow from the main result of [1]. As noted in [10, Thm. 5.4], integer hulls of bimodular integer programs can have exponential extension complexity. Moreover, Theorem 1 also does not follow from [9] since here we are dealing with arbitrary graphs G with ${\text {ocp}}(G) \leqslant 1$.

Our proof is based on a characterization of graphs with ${\text {ocp}}(G) \leqslant 1$ due to Lovász (see Seymour [11]). Kawarabayashi and Ozeki [12] later gave a short, purely graph-theoretical proof of the same result. Before stating Lovász’ theorem, we need a few more definitions.

The odd cycle transversal number of a graph G, denoted , is the minimum size of a set of nodes X such that $G - X$ is bipartite. The projective plane is the surface obtained from a closed disk by identifying antipodal points on its boundary. An embedding of a graph G in a surface is an even-face embedding if every face of G is an open disk bounded by an even cycle of G. We point out that graphs that are even-face embedded in a surface are in particular 2-connected, since the embedding yields an ear-decomposition.

Theorem 2

(Lovász, cited in [11]) Let G be a 4-connected graph with ${\text {ocp}}(G) \leqslant 1$. Then

• (i) ${\text {oct}}(G) \leqslant 3$, or

• (ii) G has an even-face embedding in the projective plane.

Note that if a graph G satisfies (i) of Theorem 2, then ${\text {STAB}}(G)$ has a linear-size extended formulation since it is the convex hull of the union of at most eight polytopes described by nonnegativity and edge constraints. If G is 4-connected and satisfies (ii), we will show that ${\text {STAB}}(G)$ admits a quadratic-size extended formulation. To this end, we will consider an affine mapping of ${\text {STAB}}(G)$ into the edge space $\mathbb {R}^{E(G)}$. This novel view allows us to identify points in $\mathbb {R}^{V(G)}$ with circulations in a certain orientation of the dual graph of G, which can be compactly described using extended formulations. This approach has been also taken in [9], where related embeddings of graphs on surfaces with higher genus were considered. As even-face embeddings refer to a slightly different notion and since the projective plane allows for much more direct arguments, we provide a self-contained proof here. This yields the proof of Theorem 1 for the case of 4-connected graphs.

For non-4-connected graphs with ${\text {ocp}}(G) \leqslant 1$ we have to address their decomposition in a non-trivial manner. We will deal with polyhedral aspects of performing 2- and 3-sums, by exploiting special properties of such graphs. We remark that for arbitrary graphs, performing multiple k-sums does not preserve small extended formulations for the respective stable set polytopes, even for $k = 2$. Note that our definition of k-sums allows some edges of the clique to be deleted (which is necessary for the proofs). If no edges of the clique are deleted during a k-sum, then it is well-known that small extended formulations are preserved by Chvátal’s clique cutset lemma [13, Theorem 4.1].

Our polyhedral analysis also crucially relies on new insights about ${\text {STAB}}(G)$ that hold for all graphs G. For example, the structure of facets of stable set polytopes (see Lemma 20), and the transformation of ${\text {STAB}}(G)$ into the edge space. We believe that this perspective can be equally beneficial for future investigations of (general) stable set polytopes.

Each step of our proof can be executed in polynomial time, and therefore the extended formulation can be constructed in polynomial time. Moreover, our proof can also be turned into a direct, purely graph-theoretic strongly polynomial time algorithm for the stable set problem in graphs G with ${\text {ocp}}(G) \leqslant 1$.

Outline In Sect. 2, we build on Theorem 2 and its signed version due to Slilaty [14] to describe the structure of graphs without two disjoint odd cycles. Roughly, we prove that each such graph G either has ${\text {oct}}(G) \le 3$ or can be obtained from a graph $H_0$ having an even-face embedding in the projective plane by gluing internally disjoint bipartite graphs $T_1$, ..., $T_\ell$ “around” $H_0$ in a certain way. Section 3 contains a proof of Theorem 1 for the case of graphs with an even-face embedding in the projective plane. The general case is treated in Sects. 4 and 5 by a delicate argument using certain gadgets $H_1$, ..., $H_\ell$ “simulating” the bipartite graphs $T_1$, ..., $T_\ell$.

2 The structure of graphs without two disjoint odd cycles

In this section we show that every graph without two disjoint odd cycles either has a small odd cycle transversal or has a structure that we will exploit later. For this purpose we use the notion of separations. A k-separation of a graph G is an ordered pair $(G_0, G_1)$ of edge-disjoint subgraphs of G with $G = G_0 \cup G_1$, $|V(G_0) \cap V(G_1)| = k$, and $E(G_0), E(G_1), V(G_1) \setminus V(G_0), V(G_0) \setminus V(G_1)$ all non-empty. We say that a k-separation is linked if for all distinct nodes u, v of $V(G_0) \cap V(G_1)$ there exists a u–v path in $G_1$ whose internal nodes are disjoint from $G_0$.

Fig. 1

A star structure

Definition 3

A star structure of a graph G is a set of subgraphs $H_0,T_1,\dots ,T_\ell$ of G such that for all $i \in [\ell ]$: $T_i$ is bipartite, $(H_0 \cup _{j \ne i} T_j, T_i)$ is a linked k-separation of G with $k \leqslant 3$, and $V(T_i) \cap V(T_j) \subseteq V(H_0)$ for all $j \ne i$ (Fig. 1).

For our structural result we will also use the notion of signed graphs. A signed graph is a pair $(G, \varSigma )$ where G is a graph and $\varSigma \subseteq E(G)$. A subgraph of G is said to be $\varSigma$-odd if it contains an odd number of edges in $\varSigma$, and is $\varSigma$-even otherwise. The odd cycle packing number of a signed graph $(G, \varSigma )$ is the maximum number of disjoint $\varSigma$-odd cycles in $(G, \varSigma )$, and is denoted by ${\text {ocp}}(G,\varSigma )$. A signed graph $(G,\varSigma )$ is balanced if ${\text {ocp}}(G, \varSigma )=0$. The odd cycle transversal number of $(G, \varSigma )$ is the minimum number of nodes in $(G, \varSigma )$ intersecting every $\varSigma$-odd cycle in $(G, \varSigma )$, and is denoted by ${\text {oct}}(G, \varSigma )$. An embedding of a signed graph $(G, \varSigma )$ in a surface is an even-face embedding if every face of $(G, \varSigma )$ is an open disk bounded by a $\varSigma$-even cycle of $(G, \varSigma )$. Graphs in this section may have parallel edges.

In the definition below, $\biguplus$ is used to denote the edge-disjoint union of graphs.

Definition 4

Let G be a graph with star structure $H_0, T_1,\dots ,T_\ell$. For each $i \in [\ell ]$, let $S_i=V(H_0) \cap V(T_i)$ and note that there is a signed clique $(K_i, \varSigma _i)$ with $V(K_i) = S_i$ such that $(K_i \biguplus T_i, \varSigma _i \biguplus E(T_i))$ is balanced. The signed graph $(H^+, \varSigma )$ is then defined via $H^+ := H_0 \biguplus K_1 \biguplus \dots \biguplus K_\ell$ and $\varSigma := E(H_0) \biguplus \varSigma _1 \biguplus \dots \biguplus \varSigma _\ell$.

The structural result is the following.

Theorem 5

Let G be a graph with ${\text {ocp}}(G) = 1$ and ${\text {oct}}(G) \geqslant 4$. Then G admits a star structure $H_0, T_1,\dots ,T_\ell$, such that $S_1, \dots , S_\ell$ and $(H^+, \varSigma )$ from Definition 4 have the following properties:

• $S_i$ is not a subset of $S_j$ for all distinct $i,j \in [\ell ]$,

• $(H^+, \varSigma )$ has an even-face embedding in the projective plane, and

• the nodes of each $S_i$ are on the boundary of some face of the embedding.

In order to obtain the above statement, we will use a finer version of Theorem 2 that is suited for signed graphs, due to Slilaty [14]. The latter result was previously known by Gerards, Lovász, and others, but [14] is the first time it appears in print.

Theorem 6

(Slilaty [14]) Let $(G, \varSigma )$ be a 4-connected signed graph with ${\text {ocp}}(G, \varSigma ) \leqslant 1$. Then

• (1) ${\text {oct}}(G, \varSigma ) \leqslant 3$ or

• (2) $(G, \varSigma )$ has an even-face embedding in the projective plane.

Lemma 7

Let G be a graph with star structure $H_0,T_1,\dots ,T_\ell$ and let $(H^+, \varSigma )$ be as in Definition 4. Then ${\text {ocp}}(H^+, \varSigma ) = {\text {ocp}}(G)$ and ${\text {oct}}(H^+, \varSigma ) \geqslant {\text {oct}}(G)$.

Proof

Let $(K_1,\varSigma _1),\dots ,(K_\ell , \varSigma _\ell )$ be as in Definition 4. We first show ${\text {ocp}}(H^+, \varSigma ) \leqslant {\text {ocp}}(G)$. Let $C_1,\dots ,C_k$ be disjoint $\varSigma$-odd cycles in $(H^+, \varSigma )$. For each $j \in [k]$ we will construct an odd cycle $C_j'$ in G by performing the following modifications to $C_j$ for each $i \in [\ell ]$. First observe that $C_j$ contains at most two edges from $K_i$. Otherwise, $C_j=K_i$ since $|V(K_i)| \leqslant 3$, which contradicts that $(K_i, \varSigma _i)$ is balanced. If $C_j$ uses only one edge uv of $K_i$, we replace uv by a u–v path $P_i$ in $T_i$ whose internal nodes are disjoint from $V(K_i)$. Note that $P_i$ exists since the separation $(H_0 \cup _{h \ne i} T_h, T_i)$ is linked. If $C_j$ uses two edges from $K_i$, say uv and vw, we replace $\{uv, vw\}$ by a u–w path $P_i$ in $T_i$. Again, $P_i$ exists by linkedness. If $C_j$ is edge-disjoint from $K_i$, we make no modification to $C_j$ for i and set $P_i=\emptyset$. Since $(K_i \uplus T_i, \varSigma _i \uplus E(T_i))$ is balanced, $|E(P_i)|$ and $|E(C_j ) \cap E(K_i) \cap \varSigma |$ have the same parity. Therefore, $|E(C_j')|$ and $|E(C_j) \cap \varSigma |$ have the same parity, and so $C_j'$ is odd. Finally, the cycles $C_1',\dots ,C_k'$ are still disjoint since for each $i \in [\ell ]$ there is at most one cycle $C_j$ that contains an edge from $K_i$ (due to $|V(K_i)| \leqslant 3)$. Thus, ${\text {ocp}}(H^+, \varSigma ) \leqslant {\text {ocp}}(G)$.

For the other inequalities, consider an arbitrary odd cycle $C'$ in G. By reversing the construction from the previous paragraph, there exists a $\varSigma$-odd cycle C in $(H^+, \varSigma )$ with $V(C) \subseteq V(C')$. It follows that ${\text {ocp}}(H^+, \varSigma ) \geqslant {\text {ocp}}(G)$ and ${\text {oct}}(H^+, \varSigma ) \geqslant {\text {oct}}(G)$. $\square$

Proof

(Proof of Theorem 5) Let G be a graph with ${\text {ocp}}(G) = 1$ and ${\text {oct}}(G) \geqslant 4$. Let $H_0,T_1,\dots ,T_\ell$ be a star structure with $( |V(H_0)|, \ell )$ lexicographically minimal. Note that such a star structure exists since G is a star structure of itself.

Suppose there exist distinct $i,j \in [\ell ]$ such that $S_j \subseteq S_i$. Since $|S_i| \leqslant 3$ and ${\text {oct}}(G) \geqslant 4$, $G - S_i$ contains an odd cycle C. Note that C is not a subgraph of $T_i \cup T_j$ because $T_i$ and $T_j$ are both bipartite and hence every odd cycle of $T_i \cup T_j$ must intersect $S_i$. Since ${\text {ocp}}(G) \leqslant 1$ this implies that $T_i \cup T_j$ is bipartite, a contradiction to the minimality of $\ell$.

Suppose $(H^+, \varSigma )$ is not 4-connected. Let $((H_1, \Upsilon _1), (H_2, \Upsilon _2))$ be a separation of $(H^+, \varSigma )$ with $X:= V(H_1) \cap V(H_2)$ and $|X| \leqslant 3$. By Lemma 7, ${\text {ocp}}(H^+, \varSigma ) = 1$ and ${\text {oct}}(H^+, \varSigma ) \geqslant 4$. Therefore, exactly one of $(H_1, \Upsilon _1)-X$ or $(H_2, \Upsilon _2)-X$ is balanced. By symmetry, we may assume that $(H_2, \Upsilon _2)-X$ is balanced, and by taking $|V(H_2)|$ to be minimal we may assume that $((H_1, \Upsilon _1), (H_2, \Upsilon _2))$ is linked. Recall that $(H^+, \varSigma )$ arises from $H_0$ by adding (balanced) signed cliques $(K_1,\varSigma _1),\dots ,(K_\ell ,\varSigma _\ell )$ corresponding to the bipartite graphs $T_1,\dots ,T_\ell$. Replacing each $(K_i, \varSigma _i)$ by the bipartite graph $T_i$, we see that G admits a star structure $H_0', T_1',\dots ,T_q'$ where $V(H_0') = V(H_1)$ , a contradiction to the minimality of $| V(H_0)|$. Since ${\text {ocp}}(H^+, \varSigma ) = 1$ and ${\text {oct}}(H^+, \varSigma ) \geqslant 4$, Theorem 6 implies that $(H^+, \varSigma )$ has an even-face embedding in the projective plane.

Suppose $S_i$ is not contained on the boundary of a face of the embedding for some $i \in [\ell ]$. Since all nodes in $S_i$ are adjacent in $(H^+, \varSigma )$, this implies $|S_i| = 3$. But now, $S_i$ is a cutset of $(H^+, \varSigma )$, contradicting that $(H^+, \varSigma )$ is 4-connected. $\square$

3 The projective planar case

In this section, we give a compact extended formulation for ${\text {STAB}}(G)$ when G has an even-face embedding in the projective plane. The results in this section follow from [9], where graphs embedded in bounded genus surfaces are considered. However, to keep our exposition self-contained, we include all proofs. Moreover, since the projective planar case is devoid of many of the technical difficulties for the bounded genus case, we hope that this section can serve as a gentler introduction to these techniques than [9].

Our starting point is the unbounded polyhedron

$$\begin{aligned} P(G) := {\text {conv}}\{ x \in \mathbb {Z}^{V(G)} \mid Mx \leqslant \mathbf {1}\}, \end{aligned}$$

where M is the edge-node incidence matrix of G. Its relationship to ${\text {STAB}}(G)$ is as follows.

Lemma 8

For every graph G, ${\text {STAB}}(G) = P(G) \cap [0,1]^{V(G)}$.

Thus, given an extended formulation for $P(G)$ we only need to add at most 2|V(G)| linear inequalities (describing $[0,1]^{V(G)})$ to obtain one for ${\text {STAB}}(G)$. To prove Lemma 8, we exploit the following result.

Lemma 9

Let G be any graph, and let $v_0$ be any fixed node of G. The projection of $P(G)$ onto the coordinates indexed by $V(G-v_0)$ equals $P(G-v_0)$.

Proof

To see that the projection of $P(G)$ is contained in $P(G-v_0)$, it suffices to prove that every integer point $x \in P(G)$ projects to a point in $P(G-v_0)$. Let $x' \in \mathbb {Z}^{V(G-v_0)}$ be the projection of x. Then, for every edge vw in $G-v_0$ we have $x'_v + x'_w = x_v + x_w \leqslant 1$ and hence $x' \in P(G-v_0)$, as claimed.

Conversely, let $x' \in \mathbb {Z}^{V(G-v_0)}$ be any integer point in $P(G-v_0)$. Consider a point $x \in \mathbb {Z}^{V(G)}$ that projects to $x'$. By decreasing $x_{v_0}$ by a sufficiently large integer amount, we may assume that $x_v + x_w \leqslant 1$ for all edges $vw \in E(G)$. Hence, x is an integer point in $P(G)$. We conclude that the projection of $P(G)$ contains $P(G-v_0)$. $\square$

Proof

(Proof of Lemma 8) It suffices to show that the polytope $P(G) \cap [0,1]^{V(G)}$ is integer. We establish this claim by induction on the number of nodes of G. The statement is clearly true if G consists of a single node. Now assume that G has at least two nodes, and the statement holds for all proper induced subgraphs of G. We have to show that it holds for G itself.

We may assume that G is connected. If not, then let $G_1$ and $G_2$ be disjoint and proper induced subgraphs of G whose union is equal to G, and in particular $P(G) = P(G_1) \times P(G_2)$. By the induction hypothesis we know that $P(G_1) \cap [0,1]^{V(G_1)}$ and $P(G_2) \cap [0,1]^{V(G_2)}$ are integer and hence $P(G) \cap [0,1]^{V(G)} = (P(G_1) \cap [0,1]^{V(G_1)}) \times (P(G_2) \cap [0,1]^{V(G_2)})$ is integer as well.

Now consider any vertex $x^*$ of $P(G) \cap [0,1]^{V(G)}$. Let $V_0 \subseteq V(G)$ denote the set of nodes v such that $x^*_v = 0$ and $V_1 \subseteq V(G)$ denote the set of nodes v such that $x^*_v = 1$.

Let us first consider the case that $V_0 = \emptyset$. We claim that also $V_1 = \emptyset$. Suppose not, so $x^*_v = 1$ for some $v \in V(G)$. Let $w \in V(G)$ be a neighbor of v. Such a node exists since G is connected and has at least two nodes. Since $x^*_w \geqslant 0$ and $x^*_v + x^*_w \leqslant 1$, we obtain $x^*_w = 0$, a contradiction to $V_0 = \emptyset$. So, in this case we would have $0< x^*_v < 1$ for all $v \in V(G)$, implying that $x^*$ is a vertex of $P(G)$. However, vertices of $P(G)$ are integer and hence we arrive at another contradiction.

Thus, there must exist a node $v_0 \in V_0$. By Lemma 9, the projection of $x^*$ onto the coordinates indexed by $V(G-v_0)$ belongs to $P(G-v_0) \cap [0,1]^{V(G-v_0)}$. By induction, this projection can be expressed as a convex combination of 0/1-points in $P(G-v_0)$. Thus, there exist stable sets $S_1,\dotsc ,S_k$ of $G-v_0$ and coefficients $\lambda _1, \dotsc , \lambda _k \in \mathbb {R}_{\geqslant 0}$ such that $\sum _{i} \lambda _i = 1$ and

$$\begin{aligned} x^*_v = \sum _{i : v \in S_i} \lambda _i \end{aligned}$$

for all $v \in V(G-v_0)$. Since $x^*_{v_0} = 0$, the equation above also holds for $v = v_0$. Now, every stable set of $G-v_0$ is also a stable set of G. It follows that $x^*$ is a convex combination of 0/1-points in $P(G)$. $\square$

Thus, it suffices to study $P(G)$ instead of ${\text {STAB}}(G)$. To this end, it is convenient to switch from the node space of G to the edge space of G by considering the affine map $\sigma : \mathbb {R}^{V(G)} \rightarrow \mathbb {R}^{E(G)}$ defined via

$$\begin{aligned} \sigma (x) := \mathbf {1}- Mx\,. \end{aligned}$$

Under $\sigma$, a vector $x \in \mathbb {R}^{V(G)}$ is mapped to $y = \sigma (x) \in \mathbb {R}^{E(G)}$ where $y_{vw} = 1 - x_v - x_w$ for every edge $vw \in E(G)$. Since $\sigma$ is invertible if and only if G has no bipartite component, we can focus on $Q(G) := \sigma (P(G))$.

We provide an extended formulation for $Q(G)$, assuming that G is even-face embedded in the projective plane. Let $G^*$ be the dual graph of G. An orientation D of the edges of $G^*$ is called alternating if in the local cyclic ordering of the edges incident to each dual node f, the edges alternatively leave and enter f. If G admits an alternating orientation of its dual graph, we will relate the points in $Q(G)$ to certain circulations in D, which, as we will see, gives rise to a compact extended formulation.

Lemma 10

Let G be a non-bipartite graph that is even-face embedded in the projective plane. Then the dual graph $G^*$ of G has an alternating orientation.

The proof of Lemma 10 relies on the fact that the parity of every cycle in G is determined by a certain topological property of the cycle. Before going into more details, we need the notion of a signature of an embedded graph.

Let G be a graph embedded in the projective plane. Each $u \in V(G)$ has a neighborhood that is a disk $\Delta _u$. By arbitrarily choosing one of the two orientations of each $\Delta _u$, we obtain a local orientation at each $u \in V(G)$. Now, take any edge $e=vw$, and let $\Delta _e$ be a disk containing e. The local orientations at v and w are either consistent or inconsistent within $\Delta _e$. We define the signature $\varSigma \subseteq E(G)$ as the set of edges $e = vw$ such that the local orientations at nodes v and w are inconsistent. Note that the signature depends on the choice of local orientations. However, it turns out that all signatures are ‘equivalent’ in a sense which we now describe.

A cycle of G is said to be 1-sided if it is $\varSigma$-odd and 2-sided otherwise. Notice that changing the local orientations at some nodes corresponds to resigning on a cut. Therefore, the property of being 1-sided or 2-sided does not depend on the local orientations, and only on the embedding of G. We point out that a cycle is 2-sided if and only if it bounds a disk. This follows from the fact that in the projective plane, 2-sided cycles are always surface separating. A proof of this fact and other basic properties of curves in the projective plane can be found in [15].

Lemma 11

Let G be a non-bipartite graph that is even-face embedded in the projective plane. Then a cycle of G is 2-sided if and only if it is even.

Proof

A cycle of G is a facial cycle if it is the boundary of a face of G. Let C be a 2-sided cycle of G. Then C bounds a closed disk $\Delta$ in the projective plane. Observe that E(C) is the symmetric difference of all E(F), where F ranges over all facial cycles of G contained in $\Delta$. Since G is even-face embedded, |E(F)| is even for all such F, and hence |E(C)| is also even.

For the other direction, let C be a 1-sided cycle of G. It is well-known that every 1-sided cycle of G is the symmetric difference of C together with some facial cycles of G. Therefore, if C is even, then every 1-sided cycle of G is even. Since we have already established that every 2-sided cycle of G is even, G is bipartite, which is a contradiction. Therefore, C is odd. $\square$

Proof

(Proof of Lemma 10) Let T be a spanning tree of G, and let $\Delta$ be a disk containing T. Pick local orientations at each node in order to put all the edges of T in the corresponding signature $\varSigma$. Seen in $\Delta$, this corresponds to picking a proper 2-coloring of T, assigning to the nodes in one color class the clockwise orientation and to the nodes in the other color class the counterclockwise orientation.

Now take any edge e of G that is not an edge of T. Let C denote the unique cycle in $T + e$. By Lemma 11, C is $\varSigma$-even if and only if C is even. Since $f \in \varSigma$ for all $f \in C \setminus \{e\}$, if follows that $e \in \varSigma$. Therefore, for this choice of local orientations, we have $\varSigma =E(G)$. We will use these local orientations to define an orientation of $G^*$ as follows.

Let F be a face of G and $v_F$ be the corresponding dual node in $G^*$. Let uv be an edge of G on the boundary of F and $uv^*$ be the corresponding dual edge in $G^*$. Let $\Delta _u$ and $\Delta _v$ be neighbourhoods of u and v such that uv intersects the boundaries of $\Delta _u$ and $\Delta _v$ exactly once, say at $u'$ and $v'$, respectively. Let $\mathbf {O_u}$ and $\mathbf {O_v}$ be the orientations of the boundaries of $\Delta _u$ and $\Delta _v$ given by the local orientations chosen for u and v. Since $uv \in \varSigma$, it follows that at $u'$ and $v'$, $\mathbf {O_u}$ and $\mathbf {O_v}$ are either both entering F or both leaving F. If they are both entering F we orient $uv^*$ towards $v_F$, and if they are both leaving F we orient $uv^*$ away from $v_F$. Since every face of G is even, note that $v_F$ is an even-degree vertex of $G^*$, and by construction, the orientation is alternating at $v_F$.

Moreover, since every edge of G is in the signature $\varSigma$, repeating the same construction for each face of G gives a well-defined alternating orientation of $G^*$. $\square$

Let G be even-face embedded in the projective plane and D be an alternating orientation of $G^*$. Note that there is a bijection between the edges of G and the arcs of D. Therefore, we may regard a vector $y \in \mathbb {R}^{E(G)}$ as a vector in $\mathbb {R}^{A(D)}$, and vice versa. With this identification, $Q(G)$ turns out to be the convex hull of all non-negative integer circulations of D that satisfy one additional constraint.

Lemma 12

Let G be a non-bipartite graph that is even-face embedded in the projective plane, D be an alternating orientation of $G^*$, and C be an arbitrary odd cycle in G. Then

$$\begin{aligned} Q(G) = {\text {conv}}\{ y \in \mathbb {Z}^{E(G)}_{\geqslant 0} \mid y \text { is a circulation in } D \text { and } y(E(C)) \text { is odd} \}. \end{aligned}$$

Proof

Setting $L := \{ y \in \mathbb {R}^{E(G)} \mid y \text { is a circulation in } D \}$, we have to show that

$$\begin{aligned} Q(G) = {\text {conv}}\{ y \in L \cap \mathbb {Z}^{E(G)}_{\geqslant 0} \mid y(E(C)) \text { is odd} \} =: Q'(G) \end{aligned}$$

holds. To this end, we first show that $\sigma (\mathbb {R}^{V(G)}) = L$ holds. To see that $\sigma (\mathbb {R}^{V(G)}) \subseteq L$ let $x \in \mathbb {R}^{V(G)}$ and consider $y = \sigma (x) \in \mathbb {R}^{E(G)}$. Let $f \in V(D)$ be any node of the dual graph. As G is even-face embedded, f is bounded by an even cycle $C_f$ in G. Let $e_1 = v_0 v_1,\, e_2 = v_1 v_2, \dots ,\, e_{2k} = v_{2k-1} v_{2k}$ denote the edges of $C_f$, where $v_0 = v_{2k}$. Note that the edges of $C_f$ correspond to the arcs of D that are incident to f. As D is alternating, we have

$$\begin{aligned} \pm \left( y(\delta ^{\mathrm {in}}(f)) - y(\delta ^{\mathrm {out}}(f)) \right) = \sum _{i=1}^{2k} (-1)^i y_{e_i} = \sum _{i=1}^{2k} (-1)^i (1 - x_{v_{i-1}} - x_{v_i}) = 0. \end{aligned}$$

Thus, y is a circulation in D and we obtain $\sigma (\mathbb {R}^{V(G)}) \subseteq L$. To see that we indeed have $\sigma (\mathbb {R}^{V(G)}) = L$, notice that $\sigma (\mathbb {R}^{V(G)})$ and L are linear subspaces, and hence it suffices to show that their dimensions coincide. To this end, we make use of Euler’s formula for the projective plane, which yields

$$\begin{aligned} |V(G)| = |E(G)| - |V(D)| + 1. \end{aligned}$$

Moreover, we need the basic fact that $\dim (L) = |E(D)| - |V(D)| + 1$. This implies

$$\begin{aligned} \dim (L) = |E(G)| - |V(D)| + 1 = |V(G)| = \dim (\mathbb {R}^{V(G)}), \end{aligned}$$

as claimed.

We next show that $Q(G) \subseteq Q'(G)$ holds. To this end, it suffices to show that for every $x \in \mathbb {Z}^{V(G)}$ with $Mx \leqslant \mathbf {1}$ the vector $y = \sigma (x) = \mathbf {1}- Mx$ is contained in $Q'(G)$. Clearly, we have $y \in \sigma (\mathbb {R}^{V(G)}) = L$ as well as $y \in \mathbb {Z}^{E(G)}_{\geqslant 0}$. It remains to show that y(E(C)) is odd. Let $e_1 = v_0 v_1,\, e_2 = v_1 v_2, \dots ,\, e_{2k+1} = v_{2k} v_{2k+1}$ denote the edges of C, where $v_0 = v_{2k+1}$. We see that

$$\begin{aligned} \sum _{i=1}^{2k} (-1)^i y_{e_i} = \sum _{i=1}^{2k} (-1)^i (1 - x_{v_{i-1}} - x_{v_i}) = 2x_{v_0} - 1 \end{aligned}$$

is odd, and so is $\sum _{i=1}^{2k} y_{e_i} = y(E(C))$.

It remains to show that $Q'(G) \subseteq Q(G)$ holds. To this end, it suffices to show that every $y \in L \cap \mathbb {Z}^{E(G)}_{\geqslant 0}$ with y(E(C)) odd is contained in $Q(G)$. As $y \in L = \sigma (\mathbb {R}^{V(G)})$ there is some $x \in \mathbb {R}^{V(G)}$ with $\mathbf {1}- Mx = \sigma (x) = y$. The nonnegativity of y implies $Mx \leqslant \mathbf {1}$. It remains to show that x is integer. As y is integer and $y_{vw} = 1 - x_v - x_w$ for every edge $vw \in E(G)$, we see that $x_v$ is integer if $x_w$ is integer for any neighbor w of v. Since G is connected it thus suffices to show that $x_v$ is integer for a single $v \in V(G)$. This holds true since $2x_{v_0} - 1 = \sum _{i=1}^{2k} (-1)^i y_{e_i}$ is an odd integer, and hence $x_{v_0}$ is integer. $\square$

In view of Lemma 12 it remains to consider the following final lemma.

Lemma 13

Let D be a directed graph with node set V and arc set A, and let $X \subseteq A$. Then the convex hull of nonnegative integer circulations y in D with y(X) odd admits an extended formulation of size O(|V||A|).

Proof

Let P denote the convex hull of nonnegative integer circulations y in D with y(X) odd. Consider the auxiliary graph $D'$ with node set $V' := V \times \{0,1\}$ and arcs from (v, p) to (w, p) for every $(v,w) \in A \setminus X$, $p \in \{0,1\}$ as well as arcs from (v, p) to $(w,1-p)$ for every $(v,w) \in A \cap X$, $p \in \{0,1\}$. For each $v \in V$ let $Q_v$ denote the polyhedron of (uncapacitated) unit flows from (v, 0) to (v, 1) in $D'$. Moreover, let Q denote the convex hull of the union of all $Q_v$ for $v \in V$. Recall that each $Q_v$ can be described using $|A'| = 2|A|$ linear inequalities (plus some linear equations) and hence, by applying Balas’ theorem [16], we obtain an extended formulation for Q of size O(|V||A|).

It remains to show that P is a linear image of Q. To this end, consider the map $\pi : \mathbb {R}^{A'} \rightarrow \mathbb {R}^A$ defined via

$$\begin{aligned} \pi (z)_{(v,w)}&:= z_{((v,0),(w,0))} + z_{((v,1),(w,1))} \quad \text {for every } (v,w) \in A \setminus X, \text { and}\\ \pi (z)_{(v,w)}&:= z_{((v,0),(w,1))} + z_{((v,1),(w,0))} \quad \text {for every } (v,w) \in A \cap X. \end{aligned}$$

For each $v \in V$ consider $P_v := \pi (Q_v)$. The recession cones of P and each $P_v$ are equal to the set of all nonnegative circulations in D, and hence the recession cones of P and $\pi (Q)$ coincide. Thus, it suffices to show that every vertex of $\pi (Q)$ is contained in P and every vertex of P is contained in $\pi (Q)$.

Let y be a vertex of $\pi (Q)$. Then it is the image of a vertex z of $P_v$ for some v. In particular, z is an integer unit flow from (v, 0) to (v, 1) in $D'$. It is now easy to check that y is a nonnegative integer circulations in D with y(X) odd.

Conversely, let y be a vertex of P. Thus, it is a nonnegative integer circulation in D with y(X) odd. Moreover, it is the characteristic vector of a directed cycle in D. Indeed, decompose $y = y_1 + \dots + y_k$ into characteristic vectors of directed cycles in D. As y(X) is odd, we may assume that $y_1(X)$ is odd. In particular $y_1 \in P$. Note that $y_2 + \dots + y_k$ is in the recession cone of P and hence, since y is a vertex of P we must have $y_2 + \dots + y_k = \mathbf {0}$.

Suppose that node v is contained in the cycle corresponding to y. Then it is easy to see that y is the image (under $\pi$) of the characteristic vector of a path from (v, 0) to (v, 1) in $D'$, and hence $y \in \pi (Q_v) \subseteq \pi (Q)$. $\square$

We are ready to prove the final result of this section.

Theorem 14

Let G be an n-node graph that is even-face embedded in the projective plane. Then ${\text {STAB}}(G)$ has a size-$O(n^2)$ extended formulation.

Proof

We may assume that G is non-bipartite since the statement is trivial otherwise. By Lemma 10, $G^*$ has an alternating orientation. As before, we denote this orientation by D.

Next, we use Lemmas 12 and 13 to obtain an extended formulation for $Q(G)$. The size of this formulation is $O(|V(D)||A(D)|) = O(n^2)$, since $|A(D)|=|E(G)|=O(n)$. This extended formulation automatically yields one for $P(G)$, since $Q(G)$ and $P(G)$ are affinely equivalent. Finally, we get a size-$O(n^2)$ extended formulation for ${\text {STAB}}(G)$ by adding the 2n inequalities $0 \leqslant x_v \leqslant 1$ for $v \in V(G)$, and invoking Lemma 8. $\square$

4 The general case

In this section, we describe how Theorem 1 can be proven using Theorems 5 and 14. Let G be a graph with ${\text {ocp}}(G) = 1$. If ${\text {oct}}(G) \leqslant 3$, then ${\text {STAB}}(G)$ has a linear-size extended formulation by Balas’ theorem [16]. Otherwise, ${\text {oct}}(G) \geqslant 4$ and G can be decomposed as in Theorem 5. In particular, G is the union of graphs $H_0, T_1, \dots , T_\ell$ where $H_0$ has an even-face embedding in the projective plane and $T_1, \dots , T_\ell$ are bipartite. Although the stable set polytopes of $H_0,T_1,\dots ,T_\ell$ admit small extended formulations and each $T_i$ intersects $H_0 \cup _{j \ne i} T_j$ in at most three nodes, it is not obvious how to obtain a small extended formulation for ${\text {STAB}}(G)$. However, in some cases it is possible to use linear descriptions of the stable set polytopes of graphs $G_1,G_2$ to obtain a description of ${\text {STAB}}(G_1 \cup G_2)$, provided that $G_1 \cap G_2$ has a specific structure, see [13, 17, 18].

With this idea in mind, recall that not only $H_0$ but also the signed graph $(H^+, \varSigma )$ has an even-face embedding in the projective plane. We will replace each signed clique used to define $(H^+, \varSigma )$ by a constant size gadget $H_i$ corresponding to each $T_i$ in a way that the resulting graph $G^{(\ell )} := H_0 \cup H_1 \cup \dots \cup H_\ell$ (the “core”) still has an even-face embedding in the projective plane. Moreover, each $T_i' := T_i \cup H_i$ will still be bipartite. In this way G is obtained from $G^{(\ell )}$ by iteratively performing k-sums with $T_1',\dots ,T_\ell '$ along $H_1, \dots , H_\ell$. In each such operation, the specific choice of the gadget will allow us to relate the extension complexities of the stable set polytopes of the participating graphs in a controlled way. Let us start with describing the gadgets that will be used.

Definition 15

A gadget is a graph isomorphic to $P_3$, $P_4$, $S_{2,2,2}$ or $S_{2,3,3}$, see Fig. 2. Let G be a graph with a linked k-separation $(G_0,G_1)$ such that $k \in \{2,3\}$ and $G_1$ is bipartite. We say that a gadget H is attachable to $G_1$ (with respect to separation $(G_0,G_1)$) if its set of leaf nodes equals $V(G_0) \cap V(G_1)$, its set of non-leaf nodes is disjoint from V(G), and $G_1 \cup H$ is bipartite.

Fig. 2

Gadgets and their names

Note that if G is a graph with a linked k-separation $(G_0,G_1)$ such that $k \in \{2,3\}$ and $G_1$ is bipartite, then there is a unique gadget $H \in \{P_3, P_4, S_{2,2,2}, S_{2,3,3}\}$ that is attachable to $G_1$.

Next, let us formally describe how the signed cliques used to define $(H^+, \varSigma )$ are replaced by gadgets in order to obtain the core.

Definition 16

Let G be a 2-connected graph with star structure $H_0, T_1,\dots ,T_\ell$. For each $i \in [\ell ]$, pick a gadget $H_i$ that is attachable to $T_i$ with respect to the separation $(H_0 \cup \bigcup _{j \ne i} T_j, T_i)$. (We always assume that the set of non-leaf nodes of the gadgets $H_i$, $i \in [\ell ]$ are mutually disjoint.) We call the graph $H_0 \cup H_1 \cup \dots \cup H_\ell$ the core.

Lemma 17

Every 2-connected graph G with ${\text {ocp}}(G) = 1$ and ${\text {oct}}(G) \geqslant 4$ admits a star structure whose core has an even-face embedding in the projective plane.

Proof

The proof is immediate by choosing a star structure that satisfies Theorem 5.

$\square$

The remaining ingredient for our proof of Theorem 1 will be the following result. To this end, let $(G_0,G_1)$ be a separation of graph G. Below, for $i \in \{0,1\}$, we call a vertex internal if it belongs to $V(G_i) \setminus V(G_{1-i})$ and an edge of $G_i$ internal if at least one of its ends is not in $G_{1-i}$.

Theorem 18

Let G be a 2-connected, non-bipartite graph. Assume that G has a k-separation $(G_0,G_1)$ such that $G_1$ is bipartite, and $k \in \{2,3\}$. Let $\mu _1$ denote the number of internal vertices and edges of $G_1$. Let H be a gadget that is attachable to $G_1$, and let $G'_0 := G_0 \cup H$. Then

Before we continue with the proof of Theorem 18 in the next section, let us see how this yields a proof of our main result.

Proof

(Proof of Theorem 1) By induction on the number of nodes n, we may assume that G is 2-connected. Indeed, suppose that G has a k-separation $(G_0,G_1)$ with $k \in \{0,1\}$. For $i \in \{0,1\}$, let $n_i := |V(G_i)|$. Thus $n = n_0 + n_1 - k$. If c is any constant such that for $i \in \{0,1\}$, we get

As observed above, if ${\text {oct}}(G) \leqslant 3$ then ${\text {STAB}}(G)$ trivially has a size-$O(n^2)$ extended formulation. Now assume that ${\text {ocp}}(G) = 1$ and ${\text {oct}}(G) \geqslant 4$. Let $H_0, T_1, \ldots , T_\ell$ be a star structure of G as in Lemma 17. Since G is 2-connected, each separation $(H_0 \cup _{j \ne i} T_j, T_i)$ is either a 2- or a 3-separation. For each $i \in [\ell ]$, we consider the graph

where $H_i$ denotes a gadget attachable to $T_i$. For $i \in [\ell ]$, let $\mu _i$ denote the number of internal vertices and edges of $T_i$. Notice that $G^{(\ell )}$ is the core, and thus by Lemma 17 has an even-face embedding in the projective plane. By Theorem 18,

Since $|V(G^{(\ell )})| = O(n)$, Theorem 14 implies . Since moreover $\sum _{i=1}^\ell \mu _i \leqslant |V(G)| + |E(G)| = O(n^2)$, we have

$\square$

5 Extended formulation for small separations

In this section we describe an extended formulation that yields the bound claimed in Theorem 18. Given a stable set S in a graph G, we say that an edge is slack if neither of its ends is in S. We denote by $\sigma (S)$ the set of slack edges, or $\sigma _G(S)$ should the graph not be clear from the context. An edge is said to be tight if it is not slack.

Lemma 19

Let G, $G_0$, $G_1$ and H be as in Theorem 18. Letting ${\overline{{\text {STAB}}}}(G_1')$ denote the convex hull of characteristic vectors of stable sets S in $G_1'$ having at most one slack edge in H, we have

(1)

where $x^0 \in \mathbb {R}^{V(G_0) \setminus V(G_1)}$, $x^1 \in \mathbb {R}^{V(G_1) \setminus V(G_0)}$, $x^{01} \in \mathbb {R}^{V(G_0) \cap V(G_1)}$ and $x^H \in \mathbb {R}^{V(H) \setminus V(G)}$.

Let us first verify that Lemma 19 indeed implies Theorem 18.

Proof

(Proof of Theorem 18) By Lemma 19, we have

Since gadget H has constant size, ${\overline{{\text {STAB}}}}(G_1')$ is the convex hull of the union of a constant number of faces of ${\text {STAB}}(G_1')$ in which the coordinates of the nodes in H are fixed. Hence by Balas’ union of polytopes [16], we obtain . Since $|V(G_1)| + |E(G_1)| - \mu _1 \leqslant 6$ and $\mu _1 \geqslant 1$, we conclude

This proves the claim. $\square$

In the proof of Lemma 19 we will exploit that the facets of stable set polytopes have a special structure, which we describe next.

5.1 Reducing to edge-induced weights

We call a weight function $w : V(G) \rightarrow \mathbb {R}$ on the nodes of G edge-induced if there is a nonnegative cost function $c : E(G) \rightarrow \mathbb {R}_{\geqslant 0}$ such that $w(v) = c(\delta (v))$ for all $v \in V(G)$. For a given node-weighted graph (G, w) we let $\alpha (G,w)$ denote the maximum weight of a stable set.

Lemma 20

Let $G = (V,E)$ be a graph without isolated nodes and let $w : V \rightarrow \mathbb {R}$ be a weight function. There exists an edge-induced weight function $w' : V \rightarrow \mathbb {R}$ such that $w(v) \leqslant w'(v)$ for all nodes v and $\alpha (G,w) = \alpha (G,w')$. In particular, the node weights of every non-trivial facet-defining inequality of ${\text {STAB}}(G)$ are edge-induced.

Proof

Let $x^*$ denote an optimal solution of the LP $\max \{\sum _{v \in V} w(v) x_v \mid x_v + x_w \leqslant 1\ \forall vw \in E,\ x \geqslant \mathbf {0}\}$ and $y^*$ be an optimal solution of its dual $\min \{\sum _{e \in E} y_e \mid y(\delta (v)) \geqslant w(v)\ \forall v \in V,\ y \geqslant \mathbf {0}\}$.

Consider the weight function $w'$ such that $w'(v) := y^*(\delta (v))$. Clearly, $w'(v) \geqslant w(v)$ for all nodes v and $w'$ is edge-induced. Consider the above LPs where $w'$ replaces w. Then $x^*$ and $y^*$ remain optimal solutions as they are feasible and satisfy complementary slackness. Moreover the values of the new LPs remain unchanged, as the objective function of the dual is not changed.

Let $V_0 := \{v \in V \mid x^*_v = 0\}$. Since $w(v) = y^*(\delta (v))$ for all $v \in V \setminus V_0$ by complementary slackness, $w(v)=w'(v)$ for all $v \in V \setminus V_0$. We have

$$\begin{aligned} \alpha (G,w) \leqslant \alpha (G,w') = \alpha (G - V_0,w') = \alpha (G - V_0, w) \leqslant \alpha (G,w)\,. \end{aligned}$$

Above, the first inequality follows from $w \leqslant w'$. The first equality follows from a result of Nemhauser and Trotter [19]. Their result implies that $(G,w')$ has a maximum weight stable set disjoint from $V_0$. The second equality follows from the fact that $w(v) = w'(v)$ for all $v \in V \setminus V_0$. Hence, equality holds throughout and $\alpha (G,w) = \alpha (G,w')$.

Finally, if $\sum _{v \in V} w(v) x_v \leqslant \alpha (G,w)$ induces a non-trivial facet of ${\text {STAB}}(G)$, there cannot exist $w' \ne w$ such that $w'\geqslant w$ and $\alpha (G,w')=\alpha (G,w)$. Hence the above argument shows that the node weights of every non-trivial facet-defining inequality of ${\text {STAB}}(G)$ are edge-induced. $\square$

In fact, in [9, Propositions 11 and 14] it is shown that one can optimize over $Q(G) = \sigma (P(G))$ instead of $\sigma ({\text {STAB}}(G))$ without changing the optimum. However, we will not need this here.

For $c : E(G) \rightarrow \mathbb {R}_{\geqslant 0}$, we let

$$\begin{aligned} \beta (G,c) := \min \left\{ \sum _{e \in E(G)} c(e) y_e \mid y \in \sigma ({\text {STAB}}(G))\right\} \,. \end{aligned}$$

(2)

Finally, we need the following easy lemma.

Lemma 21

Let $G = (V,E)$ be a graph. If $w : V(G) \rightarrow \mathbb {R}$ is induced by $c : E(G) \rightarrow \mathbb {R}_{\geqslant 0}$, then $\alpha (G,w) = c(E(G))- \beta (G,c)$.

Proof

A star of G is a set of edges of the form $\delta (v)$, for some $v \in V(G)$. Note that since $w : V(G) \rightarrow \mathbb {R}$ is induced by $c : E(G) \rightarrow \mathbb {R}_{\geqslant 0}$,

$$\begin{aligned} \alpha (G,w)=\max \{c(F) \mid \text {{ F} is the edge-disjoint union of stars}\}= c(E(G))- \beta (G,c). \end{aligned}$$

$\square$

5.2 Correctness of the extended formulation

In this section we prove Lemma 19. To this end, let R(G) denote the right-hand side of (1). Notice that for each stable set S of G, there exists a stable set $S'$ of $G' := G \cup H$ such that $S' \cap V(G) = S$ and moreover at most one edge of H is slack with respect to $S'$. The inclusion ${\text {STAB}}(G) \subseteq R(G)$ follows directly from this.

In order to prove the reverse inclusion $R(G) \subseteq {\text {STAB}}(G)$, first observe that $R(G) \subseteq \mathbb {R}^{V(G)}_{\geqslant 0}$. Thus, by Lemma 20 it suffices to show that, for all edge-induced node weights $w : V(G) \rightarrow \mathbb {R}$, the inequality

$$\begin{aligned} \sum _{v \in V(G)} w(v) x_v \leqslant \alpha (G,w) \end{aligned}$$

(3)

is valid for all $x \in R(G)$. As in Sect. 3 it will be convenient to work in the edge space instead of the node space. To this end, let $c : E(G) \rightarrow \mathbb {R}_+$ be non-negative edge costs, and let $w(v) := c(\delta (v))$ for every node v. By Lemma 21 we see that (3) is valid for R(G) if and only if

$$\begin{aligned} \sum _{e \in E(G)} c(e) y_e \geqslant \beta (G,c) \end{aligned}$$

(4)

is satisfied by all points $y \in \sigma (R(G))$. Our proof strategy to obtain (4) is to seek additional costs $c^H : E(H) \rightarrow \mathbb {R}_{\geqslant 0}$ such that

$$\begin{aligned} \sum _{e \in E(G_0)} c(e) y^0_e + \sum _{e \in E(H)} c^H(e) y^H_e \geqslant \beta (G,c) \end{aligned}$$

(5)

is valid for all $(y^0,y^H) \in \sigma ({\text {STAB}}(G'_0))$ and

$$\begin{aligned} \sum _{e \in E(G_1)} c(e) y^1_e - \sum _{e \in E(H)} c^H(e) y^H_e \geqslant 0 \end{aligned}$$

(6)

is valid for all $(y^1,y^H) \in \sigma ({\overline{{\text {STAB}}}}(G'_1))$.

We claim that this will yield (4). Indeed, for every vector $y = (y^0, y^1) \in \sigma (R(G))$ there exists a vector $y^H$ (the image of $(x^{01}, x^H)$ under $\sigma _H$) with $(y^0, y^H) \in \sigma ({\text {STAB}}(G_0'))$ and $(y^1, y^H) \in \sigma ({\overline{{\text {STAB}}}}(G'_0))$. This implies that the inequalities in (5) and (6) are satisfied. Now (4) follows since it is the sum of these two inequalities.

Let us first focus on Inequality (6). Independently of how the edge costs $c^H$ are defined, in order to prove that it holds for all $(y^0,y^H) \in \sigma ({\overline{{\text {STAB}}}}(G'_1))$, we may assume that $y^H$ is a 0/1-vector with at most one nonzero entry. The general case follows by convexity. For $F \subseteq E(H)$, we let $\chi ^F$ be the vector in $\{0,1\}^{E(H)}$ such that $\chi _e^F=1$ if and only if $e \in F$. Since the case $y^H = \mathbf {0}$ is trivial, assume that $y^H = \chi ^{\{f\}}$ for some $f \in E(H)$. Hence (6) can be rewritten as

$$\begin{aligned} \sum _{e \in E(G_1)} c(e) y^1_e \geqslant c^H(f)\,. \end{aligned}$$

(7)

This suggests the following definition of $c^H$. For $F \subseteq E(H)$, we let

$$\begin{aligned} \gamma (F):= & {} \min \left\{ c\big (\sigma (S) \cap E(G_1)\big ) \mid S \text { stable set of } G'_1,\ \sigma (S) \cap E(H) = F\right\} \\&\in \mathbb {R}_{\geqslant 0} \cup \{\infty \}\,. \end{aligned}$$

We say that F is feasible if $\gamma (F)$ is finite, that is, there exists a stable set S of $G'_1$ such that $\sigma (S) \cap E(H) = F$. Notice that $F := \{f\}$ is feasible for all $f \in E(H)$. By setting $c^H(f) := \gamma (\{f\}) \in \mathbb {R}_{\geqslant 0}$ for each $f \in E(H)$ we clearly satisfy (7), and hence (6) is valid for all $(y^1,y^H) \in \sigma ({\overline{{\text {STAB}}}}(G'_1))$ for this choice of $c^H$.

It remains to prove that with this choice of $c^H$ the inequality in (5) is valid for all $(y^0,y^H) \in \sigma ({\text {STAB}}(G'_0))$. To this end, we need the following two observations.

Lemma 22

Let $G_1$ and H be as in Theorem 18, and let $G'_1 := G_1 \cup H$. Hence, $G'_1$ is bipartite. Let $c : E(G_1) \rightarrow \mathbb {R}_{\geqslant 0}$ be nonnegative edge costs. Assume that $F \subseteq E(H)$ is feasible. Letting x and $y = (y^1,y^H)$ denote arbitrary points in $\mathbb {R}^{V(G'_1)}$ and $\mathbb {R}^{E(G'_1)}$ respectively, and letting M denote the incidence matrix of $G'_1$, consider the following LPs:

$$\begin{aligned} {\text {LP}}_1(F)&:= \min \left\{ \sum _{e \in E(G_1)} c(e) y^1_e \mid Mx + y = \mathbf {1},\ y \geqslant \mathbf {0},\ y^H = \chi ^F,\ x \geqslant \mathbf {0}\right\} \quad \text {and}\\ {\text {LP}}_2(F)&:= \min \left\{ \sum _{e \in E(G_1)} c(e) y^1_e \mid Mx + y = \mathbf {1},\ y \geqslant \mathbf {0},\ y^H = \chi ^F\right\} \,. \end{aligned}$$

Then $\gamma (F) = {\text {LP}}_1(F) = {\text {LP}}_2(F)$.

Proof

That $\gamma (F) = {\text {LP}}_1(F)$ follows directly from the fact that $G'_1$ is bipartite. Furthermore, it is clear that ${\text {LP}}_1(F) \geqslant {\text {LP}}_2(F)$. If F is empty, then ${\text {LP}}_1(F) = {\text {LP}}_2(F) = 0$ since $(x, y) := (\frac{1}{2} \mathbf {1}, \mathbf {0})$ is optimal for both LPs. From now on, assume that F is nonempty, and let $v_0 \in V(H)$ be any node that is incident to some edge of F.

Now consider the LP obtained from ${\text {LP}}_3(F)$ by adding the constraint $x_{v_0} = 0$:

$$\begin{aligned} {\text {LP}}_3(F) := \min \left\{ \sum _{e \in E(G_1)} c(e) y^1_e \mid Mx + y = \mathbf {1},\ y \geqslant \mathbf {0},\ y^H = \chi ^F,\ x_{v_0} = 0\right\} \,. \end{aligned}$$

Since $G'_1$ is bipartite, ${\text {LP}}_2(F) = {\text {LP}}_3(F)$ since adding the extra constraint does not change the set of feasible y vectors. Thanks to the extra constraint, the feasible region of ${\text {LP}}_3(F)$ is pointed.

Consider an extreme optimal solution $({\bar{x}},{\bar{y}})$ of ${\text {LP}}_3(F)$. Since M is totally unimodular, we may assume that both ${\bar{x}}$ and ${\bar{y}}$ are integral. Since F is feasible, ${\bar{x}}_v \in \{0,1\}$ for all $v \in V(H)$. We claim that $({\bar{x}},{\bar{y}})$ is feasible for ${\text {LP}}_1(F)$. Observe that the claim implies ${\text {LP}}_1(F) \leqslant {\text {LP}}_3(F) = {\text {LP}}_2(F)$ and thus ${\text {LP}}_1(F) = {\text {LP}}_2(F)$.

If ${\bar{x}}$ is nonnegative, we are done. Otherwise, we can find disjoint sets $V_{\alpha }$ and $V_{1-\alpha }$ for some $\alpha \in \mathbb {Z}_{<0}$ such that ${\bar{x}}_v = \alpha$ for all $v \in V_{\alpha }$, ${\bar{x}}_v = 1 - \alpha$ for all $v \in V_{1-\alpha }$ and no edge e with $y_e = 0$ has exactly one end in $V_{\alpha } \cup V_{1-\alpha }$. Since $\alpha < 0$ and $1 - \alpha > 1$, we see that both $V_{\alpha }$ and $V_{1-\alpha }$ are disjoint from V(H). Let ${\bar{x}}' := {\bar{x}} + \chi ^{V_{\alpha }} - \chi ^{V_{1-\alpha }}$, ${\bar{y}}' := \mathbf {1} - M{\bar{x}}'$, ${\bar{x}}'' := {\bar{x}} - \chi ^{V_{\alpha }} + \chi ^{V_{1-\alpha }}$ and ${\bar{y}}'' := \mathbf {1} - M{\bar{x}}''$. Both $({\bar{x}}',{\bar{y}}')$ and $({\bar{x}}'',{\bar{y}}'')$ are feasible for ${\text {LP}}_3(F)$, contradicting the extremality of $({\bar{x}},{\bar{y}})$. $\square$

Lemma 23

If $F \subseteq E(H)$ is feasible and the disjoint union of A and B, then $\gamma (F) \leqslant \gamma (A) + \gamma (B)$.

Proof

We may assume that A and B are both feasible, otherwise there is nothing to prove. Let (x, y) and (z, t) be optimal solutions of ${\text {LP}}_2(A)$ and ${\text {LP}}_2(B)$ respectively (see Lemma 22). If we let $u := x + z - \frac{1}{2} \mathbf {1}$ and $v := y + t$, then (u, v) is feasible for ${\text {LP}}_2(F)$ since

$$\begin{aligned} Mu + v = Mx + Mz - \frac{1}{2} M\mathbf {1} + v = (\mathbf {1} - y) + (\mathbf {1} - t) - \mathbf {1} + v = \mathbf {1}\,, \end{aligned}$$

$v \geqslant \mathbf {0}$ and $\chi ^A + \chi ^B = \chi ^F$. By Lemma 22, this shows that $\gamma (F) \leqslant \gamma (A) + \gamma (B)$.

$\square$

To prove that the inequality in (5) is valid for all $(y^0,y^H) \in \sigma ({\text {STAB}}(G'_0))$, it suffices to consider any vertex $(y^0,y^H)$ of $\sigma ({\text {STAB}}(G'_0))$ minimizing the left-hand size of (5). We may even assume that $(y^0,y^H)$ minimizes $||y^H||_1$ among all such vertices.

Let $S^0$ denote the stable set of $G'_0$ corresponding to $(y^0,y^H)$ and let $F := \sigma (S^0) \cap E(H)$. Note that $y^H = \chi ^F$. Observe that $S^0$ is not properly contained in another stable set, since this would contradict the minimality of y. Moreover, we claim that F has at most one edge. In order to prove the claim, we consider only the case where $H = S_{2,2,2}$, see Fig. 2. The other cases are easier or similar, and we leave the details to the reader.

Let us assume that F contains at least two edges, that is, $\Vert y^H\Vert _1 \geqslant 2$. We will replace $y^H$ by a new vector ${\bar{y}}^H \in \{0,1\}^{E(H)}$ such that $(y^0,{\bar{y}}^H) \in \sigma ({\text {STAB}}(G'_0))$ with smaller $\ell _1$-norm in such a way that the cost of $(y^0,{\bar{y}}^H)$ is not higher than that of $(y^0,y^H)$, arriving at a contradiction. In order to prove that $(y^0,{\bar{y}}^H) \in \sigma ({\text {STAB}}(G'_0))$ we will explain how to obtain the corresponding stable set ${\bar{S}}^0$ from stable set $S^0$ in each case. To guarantee that the cost of $(y^0,{\bar{y}}^H)$ does not exceed that of $(y^0,y^H)$, we will mainly rely on Lemma 23.

To distinguish the different cases, let $v_1$, $v_2$ and $v_3$ denote the leaves of H and $v_0$ denote its degree-3 node. For $i, j \in \{0,1,2,3\}$ we let $P_{ij}$ denote the $v_i$–$v_j$ path in H. For $i \in [3]$, let $v_{0i}$ denote the middle vertex of $P_{ij}$ and let $e_{i}$ and $f_{i}$ denote the edges of the path $P_{0i}$ incident to $v_i$ and $v_0$ respectively. The relevant cases and the replacements are listed in Fig. 3. We treat each of them below. Notice that the case $|S^0 \cap \{v_1,v_2,v_3\}| = 3$ cannot arise since this would contradict the maximality of $S^0$.

Fig. 3

Replacements in the proof of Lemma 19 (top row: before, bottom row: after). Red thick edges are slack. Blue thick, dotted edges are tight. Red nodes are in the stable set, blue nodes are not

Case 1: $|S^0 \cap \{v_1,v_2,v_3\}| = 0$. In this case we set ${\bar{y}}^H := \mathbf {0}$, which corresponds to letting ${\bar{S}}^0 := (S^0 \cup \{v_{01}, v_{02}, v_{03}\}) \setminus \{v_0\}$. In this case it is clear that the cost of $(y^0,{\bar{y}}^H)$ is at most the cost of $(y^0,y^H)$.

Case 2: $|S^0 \cap \{v_1,v_2,v_3\}| = 1$. We may assume that $S^0 \cap \{v_1,v_2,v_3\} = \{v_3\}$. Since $|F| \geqslant 2$ and $S^0$ is maximal, we must have $S^0 \cap V(H) = \{ v_0, v_3 \}$ and hence $y^H = \chi ^{\{e_1, e_2\}}$.

We let ${\bar{y}}^H := \chi ^{\{f_3\}}$, which corresponds to letting ${\bar{S}}^0 := S^0 \setminus \{v_0\} \cup \{v_{01},v_{02}\}$. The cost of $(y^0,{\bar{y}}^H)$ equals the cost of $(y^0,y^H)$ minus $\gamma (\{e_1\}) + \gamma (\{e_2\}) - \gamma (\{f_3\}) = \gamma (\{e_1\}) + \gamma (\{e_2\}) - \gamma (\{e_1,e_2\}) \geqslant 0$. The equality follows from the fact that stable sets S of $G'_1$ such that $\sigma (S) \cap E(H) = \{f_3\}$ and stable sets S of $G'_1$ such that $\sigma (S) \cap E(H) = \{e_1,e_2\}$ have the same intersection with the leaves of H. The inequality follows from Lemma 23.

Case 3: $|S^0 \cap \{v_1,v_2,v_3\}| = 2$. We may assume that $S^0 \cap \{v_1,v_2,v_3\} = \{v_1,v_2\}$. Again, since $|F| \geqslant 2$ and $S^0$ is maximal, we must have $S^0 \cap V(H) = \{ v_1,v_2,v_{03} \}$ and hence $y^H = \chi ^{\{f_1, f_2\}}$. We let ${\bar{y}}^H := \chi ^{\{e_{3}\}}$, which corresponds to letting ${\bar{S}}^0 := S^0 \setminus \{v_{03}\} \cup \{v_{01},v_{02}\}$. Similar to the previous case, we obtain that the cost of $(y^0,{\bar{y}}^H)$ equals the cost of $(y^0,y^H)$ minus $\gamma (\{f_1\}) + \gamma (\{f_2\}) - \gamma (\{e_3\}) = \gamma (\{f_1\}) + \gamma (\{f_2\}) - \gamma (\{f_1,f_2\}) \geqslant 0$.

Thus, F has indeed at most one edge. There exists a stable set $S^1$ of $G'_1$ that is a minimizer for $\gamma (F)$ such that $S^1 \cap V(G) \cap V(H) = S^0 \cap V(G) \cap V(H)$. Hence, $S := S^1 \cup S^0$ is a stable set of G. Let $(y^0,y^1)$ denote the characteristic vector of $\sigma (S)$, so that $(y^0,y^1) \in \sigma ({\text {STAB}}(G))$. We get

$$\begin{aligned} \sum _{e \in E(G_0)} c(e) y^0_e + \sum _{e \in E(H)} c^H(e) y^H_e&= \sum _{e \in E(G_0)} c(e)y^0_e + \gamma (F) \\&= \sum _{e \in E(G_0)} c(e)y^0_e + \sum _{e \in E(G_1)} c(e)y^1_e \geqslant \beta (G,c)\,. \end{aligned}$$

Above, the first equality comes from the fact that F has at most one edge, the definition of $c^H(f)$ for $f \in E(H)$ and $\gamma (\emptyset ) = 0$. The second equality follows from the hypothesis that $S^1$ is a minimizer for $\gamma (F)$. Finally, the inequality is due to the validity of (4) for $\sigma ({\text {STAB}}(G))$. This shows that (5) is indeed valid for $(y^0,y^H) \in \sigma ({\text {STAB}}(G'_0))$, which concludes the proof of Lemma 19.