We show that if the edges or vertices of an undirected graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is upper-bounded by a single-exponential function of $k$. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph $G$ and a set of $k$ pairs of vertices called terminals, asks whether $G$ can be covered by $k$ shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph $G$ and a set of $k$ terminals, asks whether there exist $\binom{k}{2}$ shortest paths covering $G$, each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter $k$.
翻译：我们证明了，如果无向图$G$的边缘或顶点可以由$k$个最短路径覆盖，则$G$的路径宽度上限为$k$的单指数函数。作为一个推论，我们证明了问题“具有终端的等距路径覆盖”（它给出一个图$G$和一组$k$对称点（称为终端），询问$G$是否可以由一个覆盖$k$个最短路径的方式覆盖，每个路径连接一对终端）是关于终端数量而言的固定参数，FPT（固定参数追踪）。在终端的类似问题中，命名为“终端的强测地集”（给定一个图$G$和一组$k$终端，问是否存在$\binom{k}{2}$个最短路径覆盖$G$，它们各自连接一个不同的终端对）。此外，这表明相关问题“等距路径覆盖”和“强测地集”（类似地定义，但是终端集不是输入的一部分）分别涉及参数$k$的XP问题。
相关内容
微信扫码咨询专知VIP会员