<p>I suppose that more specifically, you want the paths to be edge-disjoint. Cai and Ye [1] study the problem of finding two edge-disjoint paths between two (not necessarily distinct) terminal pairs. If one is to believe the preprint, this is an open problem. However, their problem is slightly more general as the terminals are allowed to be distinct. This feels quite close, but is not exactly what you asked.</p>

<hr>

<p>[1] <a href="http://www.cse.cuhk.edu.hk/~lcai/papers/edge-disjoint-path.pdf" rel="nofollow">Cai, Leizhen, and Junjie Ye. "Finding Two Edge-Disjoint Paths with Length Constraints." arXiv preprint arXiv:1509.05559 (2015).</a></p>

CC BY-SA 3.0
2016-04-14T15:33:55.853Z
Thanks Juho. However, if I understand correctly, they are looking at a more generalized problem in two senses: first, they allow a different constraint for each path, and second, they allow different $s,t$ pairs for each path.
R B
CC BY-SA 3.0
2016-04-15T13:03:30.520Z
In regard to the questions raised in the remarks of the paper offered by Juho: Instead of the original graph we can add an edge $e_{s_i}$ to $s_i$ and an edge $e_{t_i}$ to $t_i$ and then taking line graph of this newly created graph, by considering @Bart's answer, we can find $e_{s_i},e_{t_i}$ vertex disjoint paths of length at least $k_i$ in the line graph, which gives $s_i,t_i$ edge disjoint paths of length $\ge k_i$ in the original graph, on the other hand some of cases that they didn't solve are polynomial solvable, therefore all $9$ instances in that paper are FPT.
Saeed
CC BY-SA 3.0
2016-04-14T15:21:18.750Z
2016-04-14T15:51:19.097Z
2016-04-14T15:51:19.097Z
Juho
<p>Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson &amp; Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $H$ a subset of vertices in $G$, called a branch set, such that the following holds:</p>

<ul>
<li>For each $v \in V(H)$ the branch set $f(v) \subseteq V(G)$ induced a connected subgraph of $G$, and</li>
<li>The sets $f(v)$ and $f(u)$ are disjoint for $u \neq v$, and</li>
<li>For each edge $e = \{u,v\} \in E(H)$, there is an edge of $G$ between the branch set $f(u)$ and the branch set $f(v)$, and </li>
<li>The branch set of $s \in V(H)$ contains the $s$-vertex in $G$, and the branch set of $t \in V(H)$ contains the $t$-vertex in $G$.</li>
</ul>

<p>Now consider the rooted graph $H$ with roots $s$ and $t$, connected by two vertex-disjoint paths of length $k$. (So $H$ is a cycle of length $2k$ with the root vertices at distance $k$ along the cycle.) You can show that $G$ has two vertex-disjoint $st$ paths of length at least $k$ if and only if the graph $G$ with roots $s$ and $t$ has $H$ as a rooted minor. Testing rooted minors is fixed-parameter tractable parameterized by the size of $H$, which follows from <a href="http://www.sciencedirect.com/science/article/pii/S0095895685710064">Graph Minors XIII</a>. So your problem is FPT.</p>

<p>(If you are not familiar with graph minors, you might want to first absorb the fact that a graph has a cycle of length <i>at least</i> $k$ iff it contains the $k$-vertex cycle graph as a minor.)</p>

CC BY-SA 3.0
2016-04-15T10:15:49.167Z
Would you explain how checking the rooted minors follows from Graph minor XIII? checking minors directly follows from GM XIII, so e.g finding a cycle of length at least k is simply FPT, but I don't see how finding a rooted minor follows from GM XIII? maybe I missed a trivial thing. In a graph minor XIII we only have an FPT algorithm for disjoint paths problem.
Saeed
CC BY-SA 3.0
2016-04-15T10:55:02.687Z
To solve the Disjoint Paths problem, Robertson and Seymour actually show that a much more general "folio" problem can also be solved in FPT time; see Section 2 of their paper. Testing rooted minor containment is a special case of their folio problem.
Bart Jansen
CC BY-SA 3.0
2016-04-15T12:10:38.250Z
Thanks, I totally forgot that they actually solved folio problem, so your answer is nice. Just one thing, maybe you add a condition if $u\neq v$ then $f(u)\cap f(v) = \emptyset$.
Saeed
CC BY-SA 3.0
2016-04-15T14:01:30.303Z
By the way, this seems to rely heavily on the graph being undirected. Do you have a guess about digraphs?
R B
CC BY-SA 3.0
2016-04-15T08:00:38.313Z
2016-04-15T12:19:56.767Z
2016-04-15T12:19:56.767Z
Bart Jansen
<p>Consider the following problem:</p>

<blockquote>
  <p>Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$ to $t$, each of length $\ge k$.</p>
</blockquote>

<p><strong>Is there an FPT time algorithm for the above problem?</strong></p>

<hr>

<p>The problem of a single long path is known to be FPT, and so is deciding whether there exists two paths of length exactly $k$ from $s$ to $t$.</p>

<p>What happen if we combine both?</p>

CC BY-SA 3.0
2016-04-14T15:20:30.053Z
Have you tried using the color coding technique that shows that longest path problem is in FPT?
Chandra Chekuri
CC BY-SA 3.0
2016-04-14T15:35:14.667Z
@ChandraChekuri - yes. The problem is that such coloring schemes usually need the number of vertices to be coloured "correctly" to be small. Here, the two paths together may cover the entire graph.
R B
CC BY-SA 3.0
2016-04-15T04:32:27.223Z
In your problem you are not only forcing to have two paths but you also force them to have prescribed vertices. I'm not sure if the problem of long path (at least k) which goes through a specific vertex is FPT, if it is FPT, then it shouldn't be hard to provide an fpt algorithm for your problem.
Saeed
CC BY-SA 3.0
2016-04-15T05:33:21.083Z
@Saeed - I'm pretty sure you can adapt the algorithm for long cycles to find a long $(s,t)$ path in FPT time. Could you explain how you can provide an FPT algorithm for 2 long paths?
R B
CC BY-SA 3.0
2016-04-15T07:25:43.080Z
Could you explain how your claimed algorithm works? Then I'll try to modify it to provide an algorithm for two paths. Maybe I asked about it in a new thread.
Saeed
CC BY-SA 3.0
2016-04-19T09:12:04.223Z
The "$\geq k$ cycle" algorithm relies on the fact that if you have a graph with a cycle of length > 2k, then after any edge contraction, there is still a cycle of length $\geq k$. This allows you to solve the problem as follows: try to find a cycle of length exactly $k$, $k+1$, .. , $2k$ in FPT time using color coding. If you find one: you are done. Otherwise, contract an arbitrary edge and repeat. If there is a cycle of length $>> k$, contractions will eventually reduce it to a range where it is found. This fails for 2 disjoint paths, as contracting an edge may destroy the solution.
Bart Jansen
CC BY-SA 3.0
2016-06-06T00:24:42.490Z
@BartJansen Thanks for your comment. I just saw it. Your argument makes a lot of sense and it's very nice, but I'll think about it to maybe find a way to modify it in some sense.
Saeed
<cc.complexity-theory><ds.algorithms><graph-algorithms><parameterized-complexity><fixed-parameter-tractable>
Parametrized complexity of the 2-Long Paths Problem
R B
# Parametrized complexity of the 2-Long Paths Problem

(Asked by: username_0 on 2016-04-14)

Consider the following problem:

> Let $G=(V,E)$ be a graph, $s,t\in V$ vertices and $k\in\mathbb N$ an integer parameter. The 2-Long Paths Problems asks whether there exist two disjoint paths from $s$ to $t$, each of length $\ge k$.

**Is there an FPT time algorithm for the above problem?**

---

The problem of a single long path is known to be FPT, and so is deciding whether there exists two paths of length exactly $k$ from $s$ to $t$.

What happen if we combine both?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: Have you tried using the color coding technique that shows that longest path problem is in FPT?  
> **username_0**: @ChandraChekuri - yes. The problem is that such coloring schemes usually need the number of vertices to be coloured "correctly" to be small. Here, the two paths together may cover the entire graph.  
> **username_2**: In your problem you are not only forcing to have two paths but you also force them to have prescribed vertices. I'm not sure if the problem of long path (at least k) which goes through a specific vertex is FPT, if it is FPT, then it shouldn't be hard to provide an fpt algorithm for your problem.  
> **username_0**: @Saeed - I'm pretty sure you can adapt the algorithm for long cycles to find a long $(s,t)$ path in FPT time. Could you explain how you can provide an FPT algorithm for 2 long paths?  
> **username_2**: Could you explain how your claimed algorithm works? Then I'll try to modify it to provide an algorithm for two paths. Maybe I asked about it in a new thread.  
> **username_3**: The "$\geq k$ cycle" algorithm relies on the fact that if you have a graph with a cycle of length > 2k, then after any edge contraction, there is still a cycle of length $\geq k$. This allows you to solve the problem as follows: try to find a cycle of length exactly $k$, $k+1$, .. , $2k$ in FPT time using color coding. If you find one: you are done. Otherwise, contract an arbitrary edge and repeat. If there is a cycle of length $>> k$, contractions will eventually reduce it to a range where it is found. This fails for 2 disjoint paths, as contracting an edge may destroy the solution.  
> **username_2**: @BartJansen Thanks for your comment. I just saw it. Your argument makes a lot of sense and it's very nice, but I'll think about it to maybe find a way to modify it in some sense.  

---

## 2 answers

### Answer by username_3 on 2016-04-15. Score: 11 | Accepted answer

Your problem is fixed-parameter tractable, which follows from the heavy machinery of Robertson & Seymour. Your problem can be stated in terms of rooted minors. A graph $H$ with designated root vertices $s$ and $t$ is a rooted minor of a graph $G$ with roots $s$ and $t$, iff there is a function $f \colon V(H) \to 2^{V(G)}$ which assigns to each vertex of $H$ a subset of vertices in $G$, called a branch set, such that the following holds:

* For each $v \in V(H)$ the branch set $f(v) \subseteq V(G)$ induced a connected subgraph of $G$, and
* The sets $f(v)$ and $f(u)$ are disjoint for $u \neq v$, and
* For each edge $e = \{u,v\} \in E(H)$, there is an edge of $G$ between the branch set $f(u)$ and the branch set $f(v)$, and
* The branch set of $s \in V(H)$ contains the $s$-vertex in $G$, and the branch set of $t \in V(H)$ contains the $t$-vertex in $G$.

Now consider the rooted graph $H$ with roots $s$ and $t$, connected by two vertex-disjoint paths of length $k$. (So $H$ is a cycle of length $2k$ with the root vertices at distance $k$ along the cycle.) You can show that $G$ has two vertex-disjoint $st$ paths of length at least $k$ if and only if the graph $G$ with roots $s$ and $t$ has $H$ as a rooted minor. Testing rooted minors is fixed-parameter tractable parameterized by the size of $H$, which follows from [Graph Minors XIII](http://www.sciencedirect.com/science/article/pii/S0095895685710064). So your problem is FPT.

(If you are not familiar with graph minors, you might want to first absorb the fact that a graph has a cycle of length *at least* $k$ iff it contains the $k$-vertex cycle graph as a minor.)

> **Comments:**
> **username_2**: Would you explain how checking the rooted minors follows from Graph minor XIII? checking minors directly follows from GM XIII, so e.g finding a cycle of length at least k is simply FPT, but I don't see how finding a rooted minor follows from GM XIII? maybe I missed a trivial thing. In a graph minor XIII we only have an FPT algorithm for disjoint paths problem.  
> **username_3**: To solve the Disjoint Paths problem, Robertson and Seymour actually show that a much more general "folio" problem can also be solved in FPT time; see Section 2 of their paper. Testing rooted minor containment is a special case of their folio problem.  
> **username_2**: Thanks, I totally forgot that they actually solved folio problem, so your answer is nice. Just one thing, maybe you add a condition if $u\neq v$ then $f(u)\cap f(v) = \emptyset$.  
> **username_0**: By the way, this seems to rely heavily on the graph being undirected. Do you have a guess about digraphs?  

---

### Answer by username_4 on 2016-04-14. Score: 0

I suppose that more specifically, you want the paths to be edge-disjoint. Cai and Ye [1] study the problem of finding two edge-disjoint paths between two (not necessarily distinct) terminal pairs. If one is to believe the preprint, this is an open problem. However, their problem is slightly more general as the terminals are allowed to be distinct. This feels quite close, but is not exactly what you asked.

---

[1] [Cai, Leizhen, and Junjie Ye. "Finding Two Edge-Disjoint Paths with Length Constraints." arXiv preprint arXiv:1509.05559 (2015).](http://www.cse.cuhk.edu.hk/~lcai/papers/edge-disjoint-path.pdf)

> **Comments:**
> **username_0**: Thanks Juho. However, if I understand correctly, they are looking at a more generalized problem in two senses: first, they allow a different constraint for each path, and second, they allow different $s,t$ pairs for each path.  
> **username_2**: In regard to the questions raised in the remarks of the paper offered by Juho: Instead of the original graph we can add an edge $e_{s_i}$ to $s_i$ and an edge $e_{t_i}$ to $t_i$ and then taking line graph of this newly created graph, by considering @Bart's answer, we can find $e_{s_i},e_{t_i}$ vertex disjoint paths of length at least $k_i$ in the line graph, which gives $s_i,t_i$ edge disjoint paths of length $\ge k_i$ in the original graph, on the other hand some of cases that they didn't solve are polynomial solvable, therefore all $9$ instances in that paper are FPT.  

---

