论文标题
用于跟踪路径问题的多项式时间算法
Polynomial Time Algorithms for Tracking Path Problems
论文作者
论文摘要
给定图形$ g $，以及终端顶点$ s $和$ t $，跟踪路径问题要求计算要标记为跟踪器数量的最少数量的顶点，以使每个S-T路径中遇到的跟踪器顺序是唯一的。通常，跟踪路径在指示图和无向图中都是NP-HARD。在本文中，我们为某些受限版的跟踪路径提供了多项式时间算法的集合。我们证明，跟踪路径是可以解决弦图和锦标赛图的多项式时间。我们证明，跟踪路径在具有界限的最大度$δ\ geq 6 $的图中是NP-HARD，并且给出了$ 2（δ+1）$ - 相同的算法。我们还分析了跟踪S-T路径的版本，其中使用边缘而不是顶点跟踪路径，并且给出了相同的多项式时间算法。最后，我们展示了如何重建S-T路径，给定一系列跟踪器和用于图形的跟踪集。
Given a graph $G$, and terminal vertices $s$ and $t$, the TRACKING PATHS problem asks to compute a minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each s-t path is unique. TRACKING PATHS is NP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions of TRACKING PATHS. We prove that TRACKING PATHS is polynomial time solvable for chordal graphs and tournament graphs. We prove that TRACKING PATHS is NP-hard in graphs with bounded maximum degree $δ\geq 6$, and give a $2(δ+1)$-approximate algorithm for the same. We also analyze the version of tracking s-t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same. Finally, we show how to reconstruct an s-t path, given a sequence of trackers and a tracking set for the graph in consideration.
