Finding Two Edge-Disjoint Paths with Length Constraints

DOI10.1007/978-3-662-53536-3_6zbMATH Open1417.05107arXiv1509.05559OpenAlexW2963925678MaRDI QIDQ3181047

Author name not available (Why is that?)

Publication date: 22 December 2016

Published in: (Search for Journal in Brave)

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} i n l e k_{i},; = k_{i},; g e k_{i},; l e i n f t y

. 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

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 s u b s e t e q c o N P / p o l y

.

Full work available at URL: https://arxiv.org/abs/1509.05559

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Finding Two Edge-Disjoint Paths with Length Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3181047)