Uncapacitated flow-based extended formulations

Abstract

An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds on the sizes of extended formulations. Network flows are a central paradigm in discrete optimization, and are widely used to design extended formulations. We prove exponential lower bounds on the sizes of uncapacitated flow-based extended formulations of several polytopes, such as the (bipartite and non-bipartite) perfect matching polytope and TSP polytope. We also give new examples of flow-based extended formulations, e.g., for 0/1-polytopes defined from regular languages.

1 Introduction

An extended formulation (shorthand: EF) of a polytope $P \subseteq \mathbb {R}^d$ is a system of linear constraints

$$\begin{aligned} E^\leqslant x + F^\leqslant y \leqslant g^\leqslant , \quad E^= x + F^= y = g^= \end{aligned}$$

(1)

with $(x,y) \in \mathbb {R}^{d+k}$ such that $x \in \mathbb {R}^d$ belongs to $P$ if and only if there exists $y \in \mathbb {R}^k$ such that $(x,y)$ satisfies (1). An extended formulation of $P$ is simply a linear description of $P$ in an extended space. Geometrically, $P$ is described as the projection of the polyhedron¹ $Q \subseteq \mathbb {R}^{d+k}$ defined by (1). More generally, we call a polyhedron $Q \subseteq \mathbb {R}^e$ an extension (or lift) of $P$ if there exists an affine map $\pi : \mathbb {R}^e \rightarrow \mathbb {R}^d$ such that $\pi (Q) = P$.

Consider a linear description $Ax \leqslant b$ of $P$ in its original space. If $f : \mathbb {R}^d \rightarrow \mathbb {R}$ is any function, then

$$\begin{aligned} \sup \{{f(x)} \mid {Ax \leqslant b}\} = \sup \{{f(x)} \mid {E^\leqslant x + F^\leqslant y \leqslant g^\leqslant , \ E^= x + F^= y = g^=}\}. \end{aligned}$$

(2)

Thus every optimization problem on $P$ can be reformulated as an optimization problem over any extension of $P$. This is why extended formulations are interesting for optimization: in (2), the number of constraints in the right-hand side can be much smaller than the number of constraints in the left-hand side.

We define the size of an extended formulations as its number of inequalities, and the size of an extension as its number of facets; these turn out to be the right measures of size. Note that the size of an extended formulation is at least the size of the associated extension because every facet of a polyhedron is part of every linear description of this polyhedron (in the space in which it is defined), and to every extension there corresponds an extended formulation with exactly its size.

The field of extended formulations is attracting more and more attention. In particular, size lower-bounding techniques are becoming increasingly powerful and diverse, see, e.g., [4–7, 15, 16, 19, 29]. The reader will find in the surveys [11, 20, 28] a good description of the field as it was a few years ago.

In this paper, we study some restricted forms of extended formulations (extensions) which we call flow-based extended formulations (extensions), see Sect. 3 for a definition. Informally, a flow-based extension of a polytope $P$ is another polytope $Q$ that can be realized as the convex hull of all flows in some network. This definition is inspired by the prominent role played by network flows in discrete optimization: many algorithms and structural results crucially rely on network flows [1, 25]. Quite a lot of known extended formulations are based on network flows, such as those obtained from certain dynamic programming algorithms [22].

Here, we focus on uncapacitated networks. Our main contribution is to prove size lower bounds of the form $2^{\varOmega (n)}$ for uncapacitated flow-based extended formulations of the perfect matching polytope of the complete bipartite graph $K_{n,n}$, which implies similar lower bounds for the perfect matching polytope and the traveling salesman polytope of the complete graph $K_n$. Our results are summarized in Table 1. Below, the notations $O^*(\cdot )$, $\varOmega ^*(\cdot )$ and $\varTheta ^*(\cdot )$ have the same meaning as the usual notations $O(\cdot )$, $\varOmega (\cdot )$ and $\varTheta (\cdot )$, except that polynomial factors are ignored.

Table 1 Table of results

Before giving an outline of the paper, we briefly discuss our motivations. Lower bounds on restricted types of extended formulations have been studied by quite many authors, starting with the work of Yannakakis [29] on symmetric extended formulations. There has been work on hierarchies such as the Sherali–Adams [27] and Lovász–Schrijver hierarchies [21], see, e.g., [2, 8, 10, 14, 17, 24]; further work on symmetric extended formulations [5, 19, 23] and also work on extended formulations from low variance protocols [13].

We think that the restriction of being flow-based is as natural as the restrictions studied in the aforementioned papers. Combinatorial optimization offers a variety of modeling tools beyond flows, which are the most basic and important modeling tool: e.g., matchings, polymatroids and polymatroid intersections [25]. It seems a worthy research goal to characterize the expressivity of these modeling tools, and give theoretical explanations of the fact that some problems can be efficiently expressed by some modeling tools and not by others. This paper is a first step in that direction.

Of particular interest are separations between modeling tools. It is striking that all our lower bounds rely on a separation between uncapacitated and capacitated flows: while the perfect matching polytope of the complete bipartite graph $K_{n,n}$ has a $O(n^2)$-size capacitated flow-based extended formulation, we show a $\varOmega ^*(2^n)$ lower bound on the size of every uncapacitated flow-based extended formulations of that polytope. Via reductions, we derive from this the other lower bounds reported in Table 1.

The rest of the paper is organized as follows. We begin with preliminaries in Sect. 2: after introducing some notations, we define convex polytopes in general as well as the particular convex polytopes studied here. Then, in Sect. 3, we formally define flow-based extended formulations, discuss an example and establish basic properties of flow-based extended formulations, focussing on the uncapacitated case. Finally, in Sect. 4, we prove size bounds for uncapacitated flow-based extended formulations described in Table 1.

2 Preliminaries

Let $I$ be a finite ground set. The incidence vector of a subset $J \subseteq I$ is the vector $\chi ^J \in \mathbb {R}^I$ defined as

$$\begin{aligned} \chi ^J_i = \left\{ \begin{array}{ll} 1 &{}\quad \text {if } i \in J\\ 0 &{}\quad \text {if } i \notin J \end{array} \right. \end{aligned}$$

for $i \in I$. For $x \in \mathbb {R}^I$, we let $x(J) := \sum _{i \in J} x_i$.

First, let $G = (V,E)$ be an undirected graph. For a subset of vertices $U\subseteq V$, we denote as $\delta (U)$ the set of edges of $G$ with exactly one endpoint in $U$. So,

$$\begin{aligned} \delta (U)=\{uv \in E : u \in U, v \notin U\}. \end{aligned}$$

Now, let $N=(V,A)$ be a directed graph. For $U \subseteq V$, we denote by $\delta ^+(U)$ the set of arcs of $N$ with tail in $U$ and head in $V{\setminus }U$, and by $\delta ^{-}(U)$ the set of arcs of $N$ with head in $U$ and tail in $V{\setminus }U$, i.e.

$$\begin{aligned} \delta ^+(U)&= \{(u,v) \in A : u\in U, v\notin U\},\quad \text { and}\\ \delta ^-(U)&= \{(v,u) \in A : u\in U, v\notin U\}. \end{aligned}$$

As usual, for $v \in V$, we use the shortcuts $\delta (v)$, $\delta ^+(v)$ and $\delta ^-(v)$ for $\delta (\{v\})$, $\delta ^+(\{v\})$ and $\delta ^-(\{v\})$ respectively.

2.1 Convex polytopes and polyhedra

A (convex) polytope is a set $P \subseteq \mathbb {R}^d$ that is the convex hull of a finite set of points in $\mathbb {R}^d$. Equivalently, $P \subseteq \mathbb {R}^d$ is a polytope if and only if $P$ is bounded and the intersection of a finite collection of closed halfspaces. This is equivalent to saying that $P$ is bounded and the set of solutions of a finite system of linear inequalities (or equations, each of which can be represented by a pair of inequalities). A (convex) polyhedron is similar to a polytope, except that it may be unbounded. Formally, a polyhedron $Q \subseteq \mathbb {R}^d$ is any set that can be represented as the Minkowski sum of a polytope and a polyhedral cone or, equivalently, as the intersection of a finite collection of closed halfspaces. For more background on polytopes and polyhedra, see the standard reference [30].

2.2 Perfect matching polytope

A perfect matching of an undirected graph $G=(V,E)$ is set of edges $M \subseteq E$ such that every vertex of $G$ is incident to exactly one edge in $M$. The perfect matching polytope of the graph $G$ is the convex hull of the incidence vectors of the perfect matchings of $G,$ i.e.,

$$\begin{aligned} \mathop {\mathrm {P}_\mathrm {perfect\ matching}}(G) = \mathop {\mathrm {conv}}\{\chi ^M \in \mathbb {R}^E : M~ \text {perfect matching of}~ G\}. \end{aligned}$$

Edmonds [12] showed that the perfect matching polytope of $G$ is described by the following system of linear constraints (see also [26], page 438):

$$\begin{aligned} x(\delta (U))&\geqslant 1 \quad \text {for } U\subseteq V \quad \text { with }\quad |U| \text { odd},\\ \nonumber x(\delta (v))&= 1 \quad \text {for } v \in V,\\ \nonumber x_e&\geqslant 0 \quad \text {for } e\in E. \end{aligned}$$

(3)

In the case where the graph $G$ is bipartite, that is, when the vertex set $V$ can be partitioned into two sets $A$ and $B$ such that every edge in $E$ has an endpoint in $A$ and the other in $B$, the odd cut inequalities (3) may be dropped [3]. Thus the perfect matching polytope of a bipartite graph $G$ is described as follows:

$$\begin{aligned} x(\delta (v))&= 1 \quad \text {for } v \in V,\\ x_e&\geqslant 0 \quad \text {for } e\in E. \end{aligned}$$

2.3 Traveling salesman polytope

A Hamiltonian cycle of $G=(V,E)$ is a connected subgraph of $G$ such that every vertex of $G$ is incident to exactly two edges in $C$. The traveling salesman polytope of the graph $G$ is the convex hull of the incidence vectors of the hamiltonian cycles of $G,$ i.e.,

$$\begin{aligned} \mathop {\mathrm {P}_\mathrm {traveling\ salesman}}(G) = \mathop {\mathrm {conv}}\{\chi ^{E(C)} \in \mathbb {R}^E:C~\text {Hamiltonian cycle of}~G\}. \end{aligned}$$

In the formula above, $E(C)$ denotes the edge set of Hamiltonian cycle $C$.

No linear description of the traveling salesman polytope of the complete graph $K_n$ is known. Moreover no “reasonable” linear description of this polytope should be expected unless $\mathcal {NP}=\text {co-}\mathcal {NP}$ (see Corollary 5.16a [26]).

2.4 Flow polyhedron

Let $N = (V,A)$ be a network with source node $s \in V$, sink node $t \in V{\setminus }\{s\}$ and arc capacities $c_a \in \mathbb {R}_+ \cup \{\infty \}$ for $a \in A$. An $s$–$t$ flow of value $k$ is a vector $\phi \in \mathbb {R}^A$ satisfying

$$\begin{aligned} \phi (\delta ^+(v)) - \phi (\delta ^-(v))&= 0 \quad \forall v \in V{\setminus }\{s,t\},\end{aligned}$$

(4)

$$\begin{aligned} \phi (\delta ^+(s)) - \phi (\delta ^-(s))&= k,\end{aligned}$$

(5)

$$\begin{aligned} \phi _a&\geqslant 0 \quad \forall a \in A,\end{aligned}$$

(6)

$$\begin{aligned} \phi _a&\leqslant c_a \quad \forall a \in A. \end{aligned}$$

(7)

For a fixed $k \in \mathbb {R}$, the set of all $s$–$t$ flows of value $k$ in network $N$ defines a polyhedron $Q = Q(V,A,s,t,k,c)$ that we call flow polyhedron.

In this paper, we will assume most of the time that the network is uncapacitated, that is, $c_a = \infty$ for all $a \in A$. This amounts to ignoring the upper bound inequalities (7).

3 Flow-based extended formulations

3.1 Definition

Consider again a network $N = (V,A)$ with source node $s \in V$, sink node $t \in V{\setminus }\{s\}$, arc capacities $c_a \in \mathbb {R}_+ \cup \{\infty \}$ for $a \in A$ and flow value $k \in \mathbb {R}_+$. We say that the flow polyhedron $Q = Q(V,A,s,t,k,c)$ is a flow-based extension of a given polytope $P$ in $\mathbb {R}^d$ if there exists a linear projection $\pi : \mathbb {R}^A \rightarrow \mathbb {R}^d$ such that $\pi (Q) = P$. A flow-based extension is said to be uncapacitated if the associated network is uncapacitated.

From now on, we will always assume that the projection $\pi$ is linear. This causes essentially no loss of generality because an affine projection can be made linear at the cost of adding one new arc $(s',s)$ to the network and moving the source to the node $s'$. We denote by $M \in \mathbb {R}^{d \times A}$ the matrix of projection $\pi$, that is, the matrix $M\in \mathbb {R}^{d \times A}$ such that $\pi (\phi )=M\phi$ for all $\phi \in \mathbb {R}^A$.

Moreover, we denote by $F \in \mathbb {R}^{(V{\setminus }\{s,t\}) \times A}$ the coefficient matrix of the flow balance equations. In other words, $F\phi = 0$ is the matrix form of (4). Then, the flow-based extension $Q$ can be described algebraically as:

$$\begin{aligned} x = M\phi ,\ F\phi = 0,\ \phi (\delta ^+(s)) - \phi (\delta ^-(s)) = k,\ 0 \leqslant \phi \leqslant c, \end{aligned}$$

(8)

We call system (8) a flow-based extended formulation of $P$.

Notice that in the uncapacitated case, the size (that is, number of inequalities) of a flow-based extended formulation is exactly the number of arcs in the corresponding network.

Notice also that in the uncapacitated case, we can assume that $k = 1$ without loss of generality. This is because changing $k$ to $1$ simply amounts to replacing $Q$ by $(1/k)Q$. Indeed, if $\pi : \mathbb {R}^A \rightarrow \mathbb {R}^d$ projects $Q$ to $P$, then $\pi ' : \mathbb {R}^A \rightarrow \mathbb {R}^d : \phi \mapsto \pi '(\phi ) := \pi (k \phi )$ projects $(1/k)Q$ to $P$. (In case $k = 0$, $Q$ is just a point. We will ignore this case in what follows.)

We will prove below that in the uncapacitated case, we can furthermore assume that $N$ is acyclic, provided $\varnothing \subsetneq P \subseteq \mathbb {R}^d_+$. In this case, $Q$ is a polytope and its vertices are the characteristic vectors $\chi ^\sigma$ of all directed $s$–$t$ paths $\sigma$ in network $N$ (this follows from the well-known fact that the system (4)–(6) defining $Q$ is totally unimodular). We call such an extension an $s$–$t$ path extension, any corresponding extended formulation an $s$–$t$ path extended formulation and define the $s$–$t$ path extension complexity $\mathrm {xc}_{{s-t}\text { path}}(P)$ of a polytope $P$ as the minimum number of arcs of a network whose $s$–$t$ path polytope is an extension of $P$. We will show that this is also the minimum size of an uncapacitated flow-based extended formulation of $P$.

3.2 Example: regular languages

In order to convince the reader that $s$–$t$ path extensions are quite powerful, we now discuss an illustrating example that generalizes Carr and Konjevod’s flow-based extended formulation of the convex hull of even 0/1-vectors in $\mathbb {R}^n$ [9].

Consider a deterministic finite automaton $M$ over the alphabet $\{0,1\}$, that is, a $4$-tuple $(Q,\delta ,q_0,F)$ where $Q$ is now a (nonempty) finite set of states, $\delta : Q \times \{0,1\} \rightarrow Q$ is the transition function, $q_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of accept states. For a given input word $x = x_1 x_2 \ldots x_n$ in $\{0,1\}^*$ (where $\{0,1\}^*$ denotes the set of all words on the alphabet $\{0,1\}$), the automaton $M$ performs a computation starting at the initial state $q_0$ and in which the state $q_{i}$ ($i \in [n]$) is determined by the previous state $q_{i-1}$ and the $i$th letter $x_i$ of word $x$ through the equation $q_{i} = \delta (q_{i-1},x_i)$. The automaton is said to accept $x$ if the final state $q_n$ is an accept state, that is, $q_n$ belongs to $F$.

The automaton $M$ defines a language $L = L(M)$ over $\{0,1\}$ consisting of all words $x \in \{0,1\}^*$ accepted by $M$. Such a language is said to be regular. Now pick a positive integer $n$, and consider a word $x = x_1x_2 \ldots x_n$ of length $n$ in $L$. Treating each letter of word $x$ as belonging to a different coordinate, we see that $x$ defines a $0/1$-vector $(x_1,x_2,\ldots ,x_n)^\intercal$ in $\mathbb {R}^n$. By taking the convex hull of all $0/1$-vectors corresponding to all words of length $n$ in $L$, we obtain a $0/1$-polytope $P_n(L)$ in $\mathbb {R}^n$.

As we show now, one can easily construct compact flow-based extended formulations for such $0/1$-polytopes.

Proposition 1

Let $L$ denote a regular language over $\{0,1\}$ and $M = (Q,\delta ,q_0,F)$ any deterministic finite automaton recognizing the language $L$. For each positive integer $n$, there exists an $s$–$t$ path extended formulation of $P_n(L)$ with size at most $2|Q|n$.

Fig. 1

A deterministic finite automaton (left) and its corresponding network (right)

Proof

We define a network $N$ from automaton $M$. Besides source node $s$ and sink node $t$, network $N$ has $n-1$ nodes $(q,1)$, ..., $(q,n-1)$ for each state $q \in Q$. To simplify notations, we also denote $s$ by $(q_0,0)$. This defines the node set $V$ of $N$. For $i \in [n-1]$, we connect node $(q,i-1)$ to each of the nodes $(\delta (q,0),i)$ and $(\delta (q,1),i)$ by an arc. Moreover, for each transition $q ' = \delta (q,\sigma )$ with $q' \in F$ we add an arc from node $(q,n-1)$ to sink node $t$. This defines the arc set $A$ of $N$. See Fig. 1 for an example. In a formula, we have (with a slight abuse of notation because the network can have parallel arcs)

$$\begin{aligned} V&= \{\underbrace{(q_0,0)}_{= s}\} \cup \{{(q,i)} \mid {q \in Q, i \in [n-1]}\} \cup \{t\},\\ A&= \{{((q,i-1),(\delta (q,\sigma ),i))} \mid {(q,i-1) \in N, i \in [n-1], \sigma \in \{0,1\}}\}\\&\cup \{{((q,n-1),t)} \mid {\exists \sigma \in \{0,1\} : \delta (q,\sigma ) \in F}\}. \end{aligned}$$

Each arc $a \in A$ corresponds to a transition $q' = \delta (q,\sigma )$, and is said to carry the label $\sigma \in \{0,1\}$. Thus the label carried by an arc is the symbol that caused the transition.

In the network $N=(V,A)$, we send $k = 1$ units of flow from $s$ to $t$, setting all capacities $c_a$ to $\infty$. The column of the projection matrix corresponding to arc $a \in A$ from node $(q,i-1)$ is the $0/1$-vector $(0,\ldots ,0,\sigma ,0,\ldots ,0)^\intercal$ with $\sigma$ in position $i$ and $0$ everywhere else, where $\sigma \in \{0,1\}$ is the label carried by arc $a$. We leave it to the reader to perform the straightforward check that this defines an $s$–$t$ path extended formulation of $P_n(L)$.

The size of this extended formulation is the number of arcs in the network, that is,

$$\begin{aligned} 2 + 2|Q|(n-1) \leqslant 2 |Q| n. \end{aligned}$$

$\square$

3.3 Basic properties

3.3.1 Nonnegativity of the projection and acyclicity of the network

A linear projection $\pi : \mathbb {R}^A \rightarrow \mathbb {R}^d$ is called nonnegative if its projection matrix is (entry-wise) nonnegative.

Lemma 1

For every uncapacitated flow-based extension $Q \subseteq \mathbb {R}^A$, $\pi : \mathbb {R}^A \rightarrow \mathbb {R}^d$ of a nonempty polytope $P \subseteq \mathbb {R}^d_+$, there is a nonnegative linear projection $\pi ' : \mathbb {R}^A \rightarrow \mathbb {R}^d$ such that $\pi '(Q) = P$. Moreover, if the extension $Q$ is a minimum size uncapacitated flow-based extension of $P$ then the network $N=(V,A)$ is acyclic.

Proof

First, consider a directed cycle $C$ in the network $N$ and the corresponding columns of $M$. Take a point $\phi \in Q$ and consider the projection $\pi (\phi +K\chi ^C)$ where $K \in \mathbb {R}_+$. By linearity, $\pi (\phi +K\chi ^C) = \pi (\phi ) + K \pi (\chi ^C)$. If $\pi (\chi ^C)$ is a non-zero vector and $K$ is chosen large enough, $\pi (\phi )+K \pi (\chi ^C)$ would be outside of polytope $P$, a contradiction to the fact that $\phi +K\chi ^C$ satisfies (8) and thus lies in $Q$. Hence, for every directed cycle $C$ in $N$ the projection $\pi (\chi ^C)$ is a zero vector.

Now, let us prove that the projection $\pi$ may be chosen nonnegative. As above, let $M$ denote the matrix of $\pi$. It suffices to show that for every row $M_i$ of the matrix $M$ there exists a row vector $\varLambda _i \in (\mathbb {R}^{V{\setminus }\{s,t\}})^*$ such that $M_i + \varLambda _i F \geqslant 0$, since due to (8) the system $F\phi = 0$ holds for all $\phi \in Q$ and thus $(M + \varLambda F) \phi = M \phi + \varLambda F \phi = M\phi$.

Suppose, for the sake of contradiction, that no such $\varLambda _i$ exists for some $i$. Then by Farkas’ lemma, there exists a vector $\psi \in \mathbb {R}^{A}$ such that

$$\begin{aligned} F\psi = 0,\quad \psi \geqslant 0 \quad \text {and} \quad M_i \psi < 0. \end{aligned}$$

Thus $\psi$ is an $s$–$t$ flow with a non zero value or $\psi$ is a circulation in $N$. In the circulation case, $\psi$ is a union of directed cycles, and thus its projection $\pi (\psi ) = M\psi$ equals zero, violating the inequality $M_i \psi < 0$. If $\psi$ is an $s$–$t$ flow, then since the network is uncapacitated, we can assume that the value of $\psi$ is precisely $k$, by scaling $\psi$ if necessary, hence $\psi \in Q$. Now, the inequality $M_i \psi < 0$ means that the $i$th coordinate of the projection $\pi (\psi ) = M\psi$ is negative, which gives the desired contradiction.

Finally, let us show that the acyclicity of $N$ follows from the minimality of the extension $Q$. If $C$ is a directed cycle in $N$, then $\pi (\chi ^C)$ is a zero vector and due to nonegativity of $\pi$, for every arc $a\in A$ contained in at least one directed cycle, the corresponding column of $M$ is zero, that is, $\pi (\chi ^{\{a\}}) = 0$. Therefore, if $N$ contains a directed cycle, we can contract every strongly connected component of $N$ to a node and obtain a smaller flow-based extension of $P$, a contradiction. Note that if $s$ and $t$ are in the same strongly connected component of $N$, in which case we are not allowed to contract this component because we assume $s \ne t$, then necessarily $P = \{0\}$ and a minimum size flow-based extension of $P$ is given by a network with two nodes connected by a single arc. The result follows. $\square$

3.3.2 Equations for the initial polytope

Lemma 2

Let the equation $c\,x= \delta$ be valid for a nonempty polytope $P \subseteq \mathbb {R}^d$. Then for every node $v$ in the network $N=(V,A)$ associated to a minimum-size uncapacitated flow-based extension $Q \subseteq \mathbb {R}^A$ of $P$, there is a unique $\epsilon \in \mathbb {R}$ such that $c \, \pi (\chi ^\sigma )=\epsilon$ for every $s$–$v$ path $\sigma$.

Proof

Let $\sigma _1, \sigma _2$ be two paths from source $s$ to node $v$. Due to minimality of the extension there is also a path $\sigma _3$ from $v$ to $t$. Since $\sigma _1\cup \sigma _3$ and $\sigma _2\cup \sigma _3$ define paths from $s$ to $t$, the projections $\pi (\chi ^{\sigma _1\cup \sigma _3})$ and $\pi (\chi ^{\sigma _2\cup \sigma _3})$ lie in the polytope $P$, and thus satisfy the equation $c\, x = \delta$. Therefore,

$$\begin{aligned} 0= c \, \pi (\chi ^{\sigma _1\cup \sigma _3})-c \, \pi (\chi ^{\sigma _2\cup \sigma _3})=c \, \pi (\chi ^{\sigma _1}) - c \, \pi (\chi ^{\sigma _2}). \end{aligned}$$

To conclude the proof, we may define $\epsilon$ as the value $c \, \pi (\chi ^{\sigma _1})$. $\square$

3.3.3 Extension of faces

Lemma 3

For every polytope $P \ne \varnothing$ and face $F$ of $P$, there holds $\mathrm {xc}_{s-t\text { path}}(P)\geqslant \mathrm {xc}_{{s-t}\text { path}}(F)$.

Proof

Let $Q$ be a minimum size $s$–$t$ path extension of $P$ and let $N=(V,A)$ denote the corresponding network. The polytope $\pi ^{-1}(F)\cap Q$ is a face of $Q$. From the linear description of $Q$, see (4)–(6), we infer

$$\begin{aligned} \pi ^{-1}(F)\cap Q=\{{\phi \in Q} \mid {\phi _a=0,\ a\in A'}\} \end{aligned}$$

for some $A'\subseteq A$. Hence, the $s$–$t$ path polytope $Q'$ associated with the network $N'=(V, A{\setminus }A')$ together with the projection $\pi$ defines an $s$–$t$ path extension of face $F$. Because the size of the extension $Q'$ of $F$ is not larger than the size of the extension $Q$ of $P$, we have $\mathrm {xc}_{{s-t}\text { path}}(F) \leqslant \mathrm {xc}_{{s-t}\text { path}}(P)$. $\square$

4 Lower bounds

Now we provide lower bounds on the size of uncapacitated flow-based extensions or, equivalently (by Lemma 1), $s$–$t$ path extensions of the (bipartite and non-bipartite) perfect matching polytope and traveling salesman polytope. We start by proving that the $s$–$t$ path extension complexity of the perfect matching polytope of $K_{n,n}$ is $\varTheta ^*(2^n)$. This is striking because this polytope has $\varTheta (n^2)$ facets, and a size-$\varTheta (n^2)$ capacitated flow-based extension. We derive exponential lower bounds for the perfect matching polytope and traveling salesman polytope of $K_n$, by combining our lower bound on $\mathrm {xc}_{{s-t}\text { path}}(\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{n,n}))$ and Lemma 3.

4.1 Bipartite perfect matchings

Theorem 2

Every uncapacitated flow-based extension (or, equivalently, $s$–$t$ path extension) of the perfect matching polytope of the complete bipartite graph $K_{n,n}$ has size $\varOmega \textstyle {(\tfrac{2^{n}}{\sqrt{n}})}$.

Proof

Due to Lemma 1, we may assume that the projection $\pi :\mathbb {R}^{A}\rightarrow \mathbb {R}^{d}$ is given by a linear nonnegative map. Consider an $s$–$t$ path extension $Q\subseteq \mathbb {R}^{A}$ with network $N = (V,A)$ and nonnegative linear projection $\pi :\mathbb {R}^{A}\rightarrow \mathbb {R}^{d}$.

For each vertex $u$ of $K_{n,n}$, the equation

$$\begin{aligned} x(\delta (u)) = 1 \iff \sum _{e \in \delta (u)} x_e = 1 \end{aligned}$$

is valid for $\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{n,n})$. From Lemma 2, we conclude that for every node $v$ of $N$ there is a nonnegative vector $\epsilon ^v\in \mathbb {R}^{2n}$ such that for every $s$–$v$ path $\sigma$ in the network $N$ and every vertex $u$ of the graph $K_{n,n}$ the following holds:

$$\begin{aligned} \sum _{e\in \delta (u)}\pi _e(\chi ^\sigma )=\epsilon _u^v. \end{aligned}$$

We base our analysis on the support of $\epsilon ^v$, which we denote ${{\mathrm{supp}}}(\epsilon ^v)$.

Now consider a node $v$ of network $N$. For every $s$–$t$ path $\sigma$ going through $v$ and such that $\pi (\chi ^{\sigma }) = \chi ^{M}$ for some perfect matching $M$ of $K_{n,n}$, matching $M$ and cut $\delta ({{\mathrm{supp}}}(\epsilon ^v))$ do not have an edge in common, since otherwise there would be a vertex in ${{\mathrm{supp}}}(\epsilon ^v)$ which is matched by $M$ to at least two other vertices, i.e. to a vertex in ${{\mathrm{supp}}}(\epsilon ^v)$ and to a vertex in the complement of ${{\mathrm{supp}}}(\epsilon ^v)$.

Hence if ${|{{{\mathrm{supp}}}(\epsilon ^v)}|}=n$ the $s$–$t$ paths of $N$ going through $v$ define at most $\frac{n}{2}!\frac{n}{2}!$ perfect matchings $M$ of $K_{n,n}$.

Moreover, for every arc $a=(v_1,v_2)$ in $N$ with ${|{{{\mathrm{supp}}}(\epsilon ^{v_1})}|}=n_1<n$ and ${|{{{\mathrm{supp}}}(\epsilon ^{v_2})}|}=n_2>n$ there are at most $\frac{n_1}{2}!\frac{2n-n_2}{2}! \leqslant \frac{n}{2}! \frac{n}{2}!$ perfect matchings $M$ such that there is an $s$–$t$ path $\sigma$ in $N$ with $a \in \sigma$ and $\chi ^{M}=\pi (\chi ^{\sigma })$, since in this case such matching $M$ must contain all the edges from the support of $\pi (\chi ^{\{a\}})$ and must contain no edges from $\delta ({{\mathrm{supp}}}(\epsilon ^{v_1}))$ and $\delta ({{\mathrm{supp}}}(\epsilon ^{v_2}))$.

Since the polytope $Q$ is an extension of $\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{n,n})$, for every perfect matching $M$ in $K_{n,n}$ there is an $s$–$t$ path $\sigma$ such that $\chi ^\sigma$ projects to $\chi ^M$. But since $\epsilon ^{s}$ is an all-zero vector and $\epsilon ^{t}$ is an all-one vector, this path $\sigma$ must go through a node $v$ with ${|{{{\mathrm{supp}}}(\epsilon ^v)}|}=n$ or contain an arc $a = (v_1,v_2)$ with ${|{{{\mathrm{supp}}}(\epsilon ^{v_1})}|}<n<{|{{{\mathrm{supp}}}(\epsilon ^{v_2})}|}$.

Since the total number of perfect matchings in $K_{n,n}$ equals $n!$, network $N$ contains at least

$$\begin{aligned} \frac{n!}{2\frac{n}{2}!\frac{n}{2}!}=\varOmega \left( \frac{2^n}{\sqrt{n}}\right) \end{aligned}$$

nodes $v$ with ${|{{{\mathrm{supp}}}(\epsilon ^v)}|}=n$ or arcs $a=(v_1,v_2)$ with ${|{{{\mathrm{supp}}}(\epsilon ^{v_1})}|}<n<{|{{{\mathrm{supp}}}(\epsilon ^{v_2})}|}$. The result follows. $\square$

The lower bound in Theorem 2 is tight, up to polynomial factors. Ind eed, consider a complete bipartite graph $K_{n,n}$ with bipartition $U=\{u_1,\ldots , u_n\}$ and $W=\{w_1,\ldots , w_n\}$. We construct the network $N=(V,A)$ with

$$\begin{aligned} V:=2^W\qquad \text {and}\qquad A:=\{{(S_1,S_2)\in V\times V} \mid {S_1\subseteq S_2\text { and }{|{S_1}|}+1={|{S_2}|}}\} \end{aligned}$$

and a linear projection $\pi$ such that for every arc $a=(S_1,S_2)\in A$

$$\begin{aligned} \pi _{u_i,w_j}(\chi ^{\{a\}}):={\left\{ \begin{array}{ll} 1 &{} \text {if}\quad i={|{S_2}|},\quad \{w_j\}\cup S_1=S_2\\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$

It is not hard to see that every $\varnothing$–$W$ path in this network defines a perfect matching. This fact can be seen algorithmically, as follows. Start with $S=\varnothing$ and repeat the following step until $S = W$: having matched the vertices $u_1,\ldots ,u_{|{S}|}$ with the vertices in $S$, select a mate $w \in W{\setminus }\!S$ for vertex $u_{{|{S}|}+1}$ and replace $S$ by $S\cup \{w\}$. It follows that the projection of the $\varnothing$–$W$ path polytope of network $N$ coincides with the perfect matching polytope of $K_{n,n}$. Since network $N$ has $n 2^{n-1} = O^*(2^n)$ arcs, we conclude that $\mathrm {xc}_{{s-t}\text { path}}(\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{n,n})) = \varTheta ^*(2^n)$.

4.2 Nonbipartite perfect matchings

Theorem 3

Every uncapacitated flow-based extension (or, equivalently, $s$–$t$ path extension) of the perfect matching polytope of the complete graph $K_{n}$ has size $\varOmega (\frac{2^{\frac{n}{2}}}{\sqrt{n}})$.

Proof

Indeed, the polytope $\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{\frac{n}{2}, \frac{n}{2}})$ is a face of the polytope $\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_n)$, and thus Lemma 3 gives the lower bound. $\square$

In order to construct an $s$–$t$ path extension of size close to the lower bound in Theorem 3, we consider a complete graph $K_{n}$ with vertex set $U=\{u_1,\ldots , u_n\}$ and construct the network $N=(V,A)$ with

$$\begin{aligned} V&:=\{{S\subseteq U} \mid {{|{S}|}=2k,\ 0 \leqslant k\leqslant \frac{n}{2} \ \text { and }\ \forall 1 \leqslant i\leqslant k : u_i\in S}\}\\ A&:=\{{(S_1,S_2)\in V\times V} \mid {S_1\subseteq S_2\text { and }{|{S_1}|}+2={|{S_2}|}}\} \end{aligned}$$

and a linear projection $\pi$ such that for every arc $a=(S_1,S_2)\in A$

$$\begin{aligned} \pi _{u_i,u_j}(\chi ^{\{a\}})={\left\{ \begin{array}{ll} 1 &{} \text {if }\, \{u_i, u_j\}\cup S_1=S_2\\ 0 &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

It is once again easy to verify that this defines an $s$–$t$ path extension, this time of the perfect matching polytope of $K_n$. The idea is that every $\varnothing$–$U$ path in network $N$ defines a perfect matching of $K_n$ and conversely, every perfect matching of $K_n$ corresponds to at least one (actually many) $\varnothing$–$U$ path in $N$. The $\varnothing$–$U$ paths in $N$ actually correspond to perfect matchings whose edges are ordered in such a way that for each $i$, vertex $u_i$ is covered by one of the first $i$ edges in the ordering. Every arc $(S,S \cup \{u_i,u_j\})$ in such a path corresponds to the addition of edge $u_iu_j$ to the matching.

Up to a polynomial factor, the size of the network equals the number of nodes in the network, that is,

$$\begin{aligned} \sum _{k=0}^{\frac{n}{2}} \left( {\begin{array}{c}n-k\\ k\end{array}}\right) . \end{aligned}$$

This is due to the fact that the nodes $S$ in the $k$th level of network $N$ are of the form $S = \{u_1,\ldots ,u_k\} \cup T$, where $T$ is contained in $U{\setminus }\{u_1,\ldots ,u_k\}$ and has size $k$. Since the number of summands in the above expression is $\frac{n}{2}+1$, the size of the constructed extension is

$$\begin{aligned} O^*\left( \max _{0\leqslant k \leqslant \frac{n}{2}} \left( {\begin{array}{c}n-k\\ k\end{array}}\right) \right) =O^*\left( \max _{0 < k <\frac{n}{2}} \frac{(n-k)^{n-k}}{k^k (n-2k)^{n-2k}}\right) , \end{aligned}$$

where we used Stirling’s formula to simplify the left-hand side. Calculating the derivative of the function $\frac{(n-k)^{n-k}}{k^k (n-2k)^{n-2k}}$, we determine that the maximum in the above interval is achieved in the case when $k$ equals $\frac{2}{5+\sqrt{5}}n$, thus the size of the extension is $O(2^{0.695 n})$.

4.3 Hamiltonian cycles

The proof of the next theorem is inspired by Theorem 2 in [29]. Even if the proof of the next theorem is based on a similar reduction, the current proof provides a stronger lower bound (a larger base for the exponent) than the one in [29] and is presented for the sake of completeness.

Theorem 4

Every uncapacitated flow-based extension (or, equivalently, $s$–$t$ path extension) of the traveling salesman polytope of the complete graph $K_{n}$ has size $\varOmega (\frac{2^{\frac{n}{4}}}{\sqrt{n}})$.

Proof

Assume for now that $n=4k$ for some $k\in \mathbb {N}$, the other cases will be dealt with later. Take a partition of the vertices of $K_n$ in $U=\{u_1,\ldots , u_{2k}\}$ and $W=\{w_1,\ldots ,w_{2k}\}$, and consider the following sets of edges in the graph $K_n$:

$$\begin{aligned} E_0 := \{{u_iw_j} \mid {i\ne j,\, 0\leqslant i,j\leqslant 2k}\}\qquad \text {and}\qquad E_1 := \{{u_iw_i} \mid { 0\leqslant i\leqslant 2k}\}. \end{aligned}$$

Define the face $F$ of the polytope $\mathop {\mathrm {P}_\mathrm {traveling\ salesman}}(K_n)$ as the set of points in $\mathop {\mathrm {P}_\mathrm {traveling\ salesman}}(K_n)$ such that $x_e=0$ for every $e \in E_0$ and $x_e=1$ for every $e \in E_1$.

Let us show that the face $F$ together with an orthogonal projection on the variables corresponding to the edges $u_iu_j$ for $0\leqslant i,j\leqslant 2k$ gives an extension of the perfect matching polytope $\mathop {\mathrm {P}_\mathrm {perfect\ matching}}(K_{2k})$ (here the complete graph $K_{2k}$ is defined on the vertex set $U$).

First, every Hamiltonian cycle $C$ in the graph $K_n$ restricted to the edges contained in $U$ is a perfect matching, whenever $\chi ^{C}$ belongs to the face $F$. Indeed, for every vertex $u_i$ in $U$ there must be exactly two edges in $C$ adjacent to it. Since the characteristic vector $\chi ^{C}$ lies in the face $F$, one of these edges is the edge $u_iw_i$ and the other is contained in $U$.

Second, every perfect matching $M$ in the graph $K_{2k}$ can be extended to a Hamiltonian cycle $C$ in $K_n$ such that $\chi ^{C}$ lies in $F$. Indeed, extend $M$ by another perfect matching $M'$ of $K_{2k}$ to a Hamiltonian cycle in $K_{2k}$. Then the desired hamiltonian cycle $C$ can be defined as the union of $M$, $E_1$ and $\{{w_iw_j} \mid {u_iu_j \in M'}\}$. Thus the result follows from Theorem 3 and Lemma 3.

If $n=4k+r$, for some $k,r\in \mathbb {N}$, $1\leqslant r\leqslant 3$, the result is obtained in a similar way by taking a bipartition $U=\{u_1,\ldots , u_{2k}\}$ and $W=\{w_1,\ldots ,w_{2k+r}\}$ and defining the face $F$ by equations $x_e=0$ for every $e \in E_0$, $x_e=1$ for every $e \in E_1$ and $x_{w_{2k}w_{2k+1}}=\cdots =x_{w_{2k+r-1}w_{2k+r}}=1$, where the edge sets $E_0$ and $E_1$ are defined as above. $\square$

For the traveling salesman polytope there is a $s$–$t$ path extension of size $O^*(2^n)$ constructed in a similar manner as the $s$–$t$ path extension of the perfect matching polytope of $K_{n,n}$. This extension corresponds to a well-known dynamic programming algorithm of Held and Karp for the traveling salesman problem [18]. Again, we define this extension here for completeness.

Consider a complete graph $K_{n}$ with vertex set $U=\{u_1,\ldots , u_n\}$ and construct the network $N=(V,A)$ with

$$\begin{aligned} V&:= \{{(S,v)} \mid {S\subseteq U,\, v\in S, u_1\in S}\}\cup \{(U,\varnothing )\}\\ A&:= \{{((S_1,v_1),(S_2,v_2))\in V\times V} \mid {S_1\cup \{v_2\}=S_2\text { and }{|{S_1}|}+1={|{S_2}|}}\}\\&\cup \,\{{((U,v),(U,\varnothing ))\in V\times V} \mid {v\in U}\} \end{aligned}$$

and a linear projection $\pi$ such that for every arc $a=((S_1,v_1),(S_2,v_2))\in A$, $v_1\in U$, $v_2\in U$

$$\begin{aligned} \pi _{u_i,u_j}(\chi ^{\{a\}}):={\left\{ \begin{array}{ll} 1 &{} \text {if }\, \{u_i, u_j\}=\{v_1,v_2\}\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

and for an arc $a=((U,v),(U,\varnothing ))\in A$, $v\in U$

$$\begin{aligned} \pi _{u_i,u_j}(\chi ^{\{a\}}):={\left\{ \begin{array}{ll} 1 &{} \text {if }\,\{u_i, u_j\}=\{u_1,v\} \\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$

It is straightforward to see that the network with source $(u_1,\{u_1\})$ and sink $(U,\varnothing )$ generates the desired $s$–$t$ path extension.