<p>Your solution might consist of a path plus several edge-disjoint cycles.</p>

CC BY-SA 3.0
2013-10-23T12:05:05.613Z
2013-10-23T12:05:05.613Z
Jeffε
<p>I have a directed graph which has cycles.  Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$.  Simple means the path has no repetition in vertices.</p>

<p>I understand this problem is NP-hard in general.  But I am wondering what's wrong in my following linear programming formulation.</p>

<p>Let us add a source vertex $s$, which is connected to $u$ by an edge with capacity $1$. Let v be connected to a sink vertex $t$ with capacity 1 too.  Denote the new edge set as $E$.  Use $w_{ij} = 1$ to represent that the edge $(i,j)$ is in the path, and $w_{ij} = 0$ if not. So $w_{ij} \in \{0,1\}$.  Then a simple path from $s$ to $t$ needs to satisfy</p>

<ol>
<li><p>Conservation constraints: for all vertices $i$ (except $s$ and $t$),</p>

<p>$\sum_{k: (k, i) \in E} w_{ki} = \sum_{j: (i,j) \in E} w_{ij}$.</p>

<p>Let us call this common quantity as $w_i$.</p></li>
<li><p>No repetition of vertex: add a vertex capacity 1 on each vertex:</p>

<p>$w_i \in \{0,1\}$.</p></li>
</ol>

<p>Clearly any set of $\{w_{ij}\}$ satisfying these constraints represents an st-path, as long as $w_{ij}$ is not straight $0$.  </p>

<p>Now let us drop the integral constraints:</p>

<p>$w_{ij} \in [0,1]$, $w_i \in [0,1]$,</p>

<p>$w_i = \sum_{k: (k, i) \in E} w_{ki}$  for all $i$,</p>

<p>$w_i = \sum_{j: (i,j) \in E} w_{ij}$  for all $i$.</p>

<p>Then I claim the coefficient matrix arising from these linear constraints is totally unimodular (TUM).  To this end, it suffices to show that the coefficient matrix for the last two constraints is TUM. But this is trivial, say by the example 1 of <a href="http://en.wikipedia.org/wiki/Unimodular_matrix#Common_totally_unimodular_matrices" rel="nofollow">this link</a> (take $B$ as the set of all rows, and $C$ as an empty set).</p>

<p>Since a longest path maximizes a linear function of $w_{ij}$ with positive coefficients, the optimal solution must be an extreme point of the feasible region, which by TUM must be integral.  Clearly, setting $w_{ij}$ to straight 0 is not optimal, and so the optimal solution must be an $st$-path.</p>

<p>So question: something must be wrong here, either</p>

<ol>
<li><p>The integral constraints in 1 and 2 do not jointly define an $st$-path (ignoring the straight 0), and/or</p></li>
<li><p>TUM does not hold indeed.</p></li>
</ol>

CC BY-SA 3.0
2013-10-23T12:05:50.927Z
This is not a research-level question; it would be better for CS.se.
Jeffε
<graph-algorithms><shortest-path>
What's wrong with my linear programming formulation of longest path?
Janathan
# What's wrong with my linear programming formulation of longest path?

(Asked by: username_0 on 2013-10-23)

I have a directed graph which has cycles. Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$. Simple means the path has no repetition in vertices.

I understand this problem is NP-hard in general. But I am wondering what's wrong in my following linear programming formulation.

Let us add a source vertex $s$, which is connected to $u$ by an edge with capacity $1$. Let v be connected to a sink vertex $t$ with capacity 1 too. Denote the new edge set as $E$. Use $w\_{ij} = 1$ to represent that the edge $(i,j)$ is in the path, and $w\_{ij} = 0$ if not. So $w\_{ij} \in \{0,1\}$. Then a simple path from $s$ to $t$ needs to satisfy

1. Conservation constraints: for all vertices $i$ (except $s$ and $t$),

   $\sum\_{k: (k, i) \in E} w\_{ki} = \sum\_{j: (i,j) \in E} w\_{ij}$.

   Let us call this common quantity as $w\_i$.
2. No repetition of vertex: add a vertex capacity 1 on each vertex:

   $w\_i \in \{0,1\}$.

Clearly any set of $\{w\_{ij}\}$ satisfying these constraints represents an st-path, as long as $w\_{ij}$ is not straight $0$.

Now let us drop the integral constraints:

$w\_{ij} \in [0,1]$, $w\_i \in [0,1]$,

$w\_i = \sum\_{k: (k, i) \in E} w\_{ki}$ for all $i$,

$w\_i = \sum\_{j: (i,j) \in E} w\_{ij}$ for all $i$.

Then I claim the coefficient matrix arising from these linear constraints is totally unimodular (TUM). To this end, it suffices to show that the coefficient matrix for the last two constraints is TUM. But this is trivial, say by the example 1 of [this link](http://en.wikipedia.org/wiki/Unimodular_matrix#Common_totally_unimodular_matrices) (take $B$ as the set of all rows, and $C$ as an empty set).

Since a longest path maximizes a linear function of $w\_{ij}$ with positive coefficients, the optimal solution must be an extreme point of the feasible region, which by TUM must be integral. Clearly, setting $w\_{ij}$ to straight 0 is not optimal, and so the optimal solution must be an $st$-path.

So question: something must be wrong here, either

1. The integral constraints in 1 and 2 do not jointly define an $st$-path (ignoring the straight 0), and/or
2. TUM does not hold indeed.

**Tags:** graph-algorithms, shortest-path
> **Comments:**
> **username_1**: This is not a research-level question; it would be better for CS.se.  

---

## 1 answers

### Answer by username_1 on 2013-10-23. Score: 4 | Accepted answer

Your solution might consist of a path plus several edge-disjoint cycles.


---

