Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints

Question

This is a homework problem for a class that ended 2 years ago, I'm learning it by myself.

Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\{a_1,\ldots,a_n\}$. Let $P=\{p_1,\ldots,p_m\}$ be the set of all simple paths from $s$ to $t$, There is a capacity function $c:A\to \mathbb{R}^+$. First we are asked to express max s-t flow as a linear program letting each path $p_j$ in $P$ associated with the variable $x_j$, there could be a exponential number of variables.

The formulation, $$ \begin{align} \text{Maximize:} & \sum_{j}x_j\\ \text{subject to:} & \sum_{a_i \in p_j}{x_j} \leq c(a_i) &\text{ for } 1 \le i \le n, \\ & x_j\geq 0 &\text{ for } 1 \leq j \leq m\\ \end{align} $$

The dual is therefore: $$ \begin{align} \text{Minimize:} & \sum_{i} c(a_i) y_i\\ \text{subject to:} & \sum_{a_i\in p_j} y_i \geq 1 &\text{ for } 1 \le j \le m, \\ & y_i\geq 0 &\text{ for } 1 \leq i \leq n\\ \end{align} $$

Assuming we have an optimal solution for the dual, the problem ask us to use complementary slackness to show there exist a formulation of the primal with only a polynomial number of paths, which also obtain an optimal solution. How is this done?

Answer 1

One way which comes to mind is to use the fact that if $\sum_{a_i \in p_j} y_i > 1$ for some $j \in [m]$ then $x_j = 0$ and so the path $p_j$ is irrelevant. However, consider a graph with exponentially many paths in which the source has capacity 1 and all other vertices have capacity 2. The optimal solution is 1 and it is obtained by $y_s = 1$ and $y_v = 0$ for all $v \neq s$, and so all the inequalities considered above are tight. (For a "generic" graph, however, we can expect the optimal solution to be obtained at a vertex, and so have at most $n$ tight constraints.)

Another way is to notice that if the primal has an optimal solution then it has one which is a vertex, and so has at least $m$ tight inequalities. At least $m-n$ of them are of the type $x_j \geq 0$, and so there is an optimal solution using at most $n$ paths. However this is not helpful in the context of the exercise.