Prev: Can I solve 1-in-3 3-SAT in polynomial time?
Next: paritioning an array evenly without moving data
From: stone on 25 Jun 2008 03:51
There is a n vertices directed graph consisting of two types of edge,
forward edges and backward edges.
A forward edge is a directed edge from vertex i to vertex j such that
i<j.
A backward edge is a directed edge from vertex i to vertex j such that
i>j.
Decide whether there exists a simple path (no duplicated vertex) from
vertex 1 to vertex n containing
at least one backward edge.

Can anybody give me some suggestion or related papers?
Thanks in advance.
From: POLAND on 25 Jun 2008 08:19

It's polynomial, though I can only provide an O(E^2) algorithm, and it
certainly could be done better. It is enough to answer a slightly
simpler question:

(*) For a fixed edge (u,v), is there a simple path from 1 to n
containing (u,v)?

If you could do that in polynomial time, you can loop through all
backward edges, which provides a general answer for your question.

However, the (*) condition is equivalent to:

(**) Do there exist two vertex-disjoint paths, one from 1 to u, the
other from v to n?

which, by adding two artificial vertices s,t and edges (s,1), (s,v),
(u,t), (n,t), transforms to:

Do there exist two vertex-disjoint paths from s to t?

The last one is a simple connectivity problem, easily solvable in O(E)
time using flows.

--
Lech Duraj
From: stone on 25 Jun 2008 09:06
On Jun 25, 8:19 pm, POLAND <""lduraj\"@poczta.onet.(POLAND)"> wrote:
> It's polynomial, though I can only provide an O(E^2) algorithm, and it
> certainly could be done better. It is enough to answer a slightly
> simpler question:
>
> (*) For a fixed edge (u,v), is there a simple path from 1 to n
> containing (u,v)?
>
> If you could do that in polynomial time, you can loop through all
> backward edges, which provides a general answer for your question.
>
> However, the (*) condition is equivalent to:
Network flow techniques seem not applicable to the problem below.

(**) Do there exist two vertex-disjoint paths, one from 1 to u, the
other from v to n?
which, by adding two artificial vertices s,t and edges (s,1), (s,v),
(u,t), (n,t), transforms to:

By your method, it possible to obtain two vertex disjoint paths s-->1--
>n-->t and s-->v--->u-->t.
But it's not that we want.

Thanks for your concern all the same.

>
> (**) Do there exist two vertex-disjoint paths, one from 1 to u, the
> other from v to n?
>
> which, by adding two artificial vertices s,t and edges (s,1), (s,v),
> (u,t), (n,t), transforms to:
>
> Do there exist two vertex-disjoint paths from s to t?
>
> The last one is a simple connectivity problem, easily solvable in O(E)
> time using flows.
>
> --
> Lech Duraj

 | 
Pages: 1
Prev: Can I solve 1-in-3 3-SAT in polynomial time?
Next: paritioning an array evenly without moving data