论文标题
改进的核跟踪路径问题
Improved Kernels for Tracking Path Problem
论文作者
论文摘要
跟踪移动对象对于安全系统和网络至关重要。给定图形$ g $，终端顶点$ s $和$ t $，以及一个整数$ k $，\ textsc {跟踪路径}问题询问是否存在最多$ k $ pertices，如果标记为跟踪器，则确保每个S-T路径中遇到的跟踪器的顺序是独一无二的。众所周知，该问题是NP-HARD，并以$ \ MATHCAL {O}（k^6）$ VERTICES和$ \ MATHCAL {O}（k^7）$ edges接纳了一个内核（可还原为等效实例），当由输出（跟踪集）$ k $ [5]进行参数时。仍然开放的一个有趣的问题是是否可以改善现有内核。在本文中，我们肯定地回答了：（i）对于一般图，我们显示了大小$ \ Mathcal {o}（k^2）$，（ii）的核的存在，对于平面图，我们通过给出大小$ \ Mathcal {o}（o}（o}（k）$）的核。此外，我们还表明，当通过$ k $参数化时，在$ n $ vertices上找到最多$ n-k $的尺寸跟踪集[1]。
Tracking of moving objects is crucial to security systems and networks. Given a graph $G$, terminal vertices $s$ and $t$, and an integer $k$, the \textsc{Tracking Paths} problem asks whether there exists at most $k$ vertices, which if marked as trackers, would ensure that the sequence of trackers encountered in each s-t path is unique. It is known that the problem is NP-hard and admits a kernel (reducible to an equivalent instance) with $\mathcal{O}(k^6)$ vertices and $\mathcal{O}(k^7)$ edges, when parameterized by the size of the output (tracking set) $k$ [5]. An interesting question that remains open is whether the existing kernel can be improved. In this paper we answer this affirmatively: (i) For general graphs, we show the existence of a kernel of size $\mathcal{O}(k^2)$, (ii) For planar graphs, we improve this further by giving a kernel of size $\mathcal{O}(k)$. In addition, we also show that finding a tracking set of size at most $n-k$ for a graph on $n$ vertices is hard for the parameterized complexity class W[1], when parameterized by $k$.
