6
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Have you tried using the color coding technique that shows that longest path problem is in FPT? $\endgroup$
    – Chandra Chekuri
    Apr 14, 2016 at 15:20
  • $\begingroup$ @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. $\endgroup$
    – R B
    Apr 14, 2016 at 15:35
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 15, 2016 at 4:32
  • $\begingroup$ @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? $\endgroup$
    – R B
    Apr 15, 2016 at 5:33
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 15, 2016 at 7:25

2 Answers 2

Reset to default
11
$\begingroup$

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. 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.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 15, 2016 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – Bart Jansen
    Apr 15, 2016 at 10:55
  • $\begingroup$ 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$. $\endgroup$
    – Saeed
    Apr 15, 2016 at 12:10
  • $\begingroup$ By the way, this seems to rely heavily on the graph being undirected. Do you have a guess about digraphs? $\endgroup$
    – R B
    Apr 15, 2016 at 14:01
0
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – R B
    Apr 14, 2016 at 15:33
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 15, 2016 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.