

























We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph $G$, two vertices $s$ and $t$ of $G$, and a non-negative integer $k$, and the objective is to determine whether $G$ contains a path of length at least $dist_G(s,t) +k$ where $dist_G(s,t)$ is the length of a shortest path from $s$ to $t$ in $G$ (assuming that one exists). We show that the problem is fixed parameter tractable (FPT) parameterized by $k$ in the class of graphs where {\sc $2$-Disjoint Paths} problem is polynomial time solvable.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。