论文标题
在可覆盖的图表上最短路径
On graphs coverable by k shortest paths
论文作者
论文摘要
我们表明，如果$ k $最短路径可以覆盖无向图$ g $的边缘或顶点，则$ g $的路径宽是由$ k $的单个指数函数限制的。作为推论，我们证明了带有终端的问题等距路径覆盖率（鉴于图形$ g $和一组$ k $的顶点，称为终端，问$ g $是否可以由$ k $最短路径覆盖，每个路径都可以覆盖，每个路径都与终端数量相关。对于类似的问题，具有终端的强烈测量集（给定图形$ g $和一组$ k $终端）询问是否存在$ \ binom {k} {2} $最短路径覆盖$ g $，每个终端是否存在$ g $，每个终端都有相同的终端）。此外，这意味着相关问题等距路径覆盖范围和强大的大地测量集（定义类似，但终端集不属于输入的一部分）在XP中与参数$ k $有关。
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$.
