5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your second solution is great. I was using the other side of complementary slackness, $y_i\neq 0$ then $\sum_{a_i \in p_j} x_j = c(a_i)$. This give us a set of linear equality to solve. If one can show there is a solution with polynomial number of non-zero $x_j$'s to those equalities then it would be an optimal solution, which I still haven't figure out how. $\endgroup$ – Chao Xu Jun 23 '13 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.