论文标题
用于跟踪最短路径的多项式内核
Polynomial Kernels for Tracking Shortest Paths
论文作者
论文摘要
给定无向图$ g =（v，e）$，顶点$ s，t in v $和一个整数$ k $，跟踪最短路径需要确定是否存在一组$ k $ theTices $ t \ subseteq v $ v（p_1）\ neq t \ cap v（p_2）$。在本文中，我们为问题提供了第一个多项式尺寸内核。具体而言，我们显示了具有$ \ MATHCAL {O}（k^2）的内核的存在，$ pertices and Edges and Edges in Constrice Graphs中的边缘和带有$ \ Mathcal {O}（k）$ pertices和Edges的内核，用于dag问题中的跟踪路径的平面图中的tertices and Edges。这个问题承认了多项式参数转换到跟踪最短路径，这意味着具有$ \ MATHCAL {O}（k^4）的内核，用于跟踪一般图中最短路径的最短路径和带有$ \ Mathcal {O}（O}（k^2）$ Vertices和Edges和Edge的内核。基于上述，我们还提供了一种指数算法，用于跟踪平面图中的最短路径。
Given an undirected graph $G=(V,E)$, vertices $s,t\in V$, and an integer $k$, Tracking Shortest Paths requires deciding whether there exists a set of $k$ vertices $T\subseteq V$ such that for any two distinct shortest paths between $s$ and $t$, say $P_1$ and $P_2$, we have $T\cap V(P_1)\neq T\cap V(P_2)$. In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with $\mathcal{O}(k^2)$ vertices and edges in general graphs and a kernel with $\mathcal{O}(k)$ vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with $\mathcal{O}(k^4)$ vertices and edges for Tracking Shortest Paths in general graphs and a kernel with $\mathcal{O}(k^2)$ vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.
