Finding Two Edge-Disjoint Paths with Length Constraints

Leizhen Cai; Junjie Ye

paper

Finding Two Edge-Disjoint Paths with Length Constraints

arXiv:1509.05559

Abstract

We consider the problem of finding, for two pairs $(s_{1}, t_{1})$ and $(s_{2}, t_{2})$ of vertices in an undirected graphs, an $(s_{1}, t_{1})$ -path $P_{1}$ and an $(s_{2}, t_{2})$ -path $P_{2}$ such that $P_{1}$ and $P_{2}$ share no edges and the length of each $P_{i}$ satisfies $L_{i}$ , where $L_{i} \in {\leq k_{i}, = k_{i}, \geq k_{i}, \leq \infty}$ . We regard $k_{1}$ and $k_{2}$ as parameters and investigate the parameterized complexity of the above problem when at least one of $P_{1}$ and $P_{2}$ has a length constraint (note that $L_{i} = " \leq \infty"$ indicates that $P_{i}$ has no length constraint). For the nine different cases of $(L_{1}, L_{2})$ , we obtain FPT algorithms for seven of them. Our algorithms uses random partition backed by some structural results. On the other hand, we prove that the problem admits no polynomial kernel for all nine cases unless $N P \subseteq co N P / p o l y$ .