论文标题
跟踪路径问题的结构参数化
Structural Parameterizations of Tracking Paths Problem
论文作者
论文摘要
给定带有源和目标顶点$ s，t \ in v（g）$的图形$ g $，\ textsc {跟踪路径}要求最小的一组顶点$ t \ subseteq v（g）$，以使从$ s $ to $ t $唯一的简单路径中遇到的顶点序列是唯一的。该问题被证明\ textsc {np} -hard \ cite {tr-j}，并在通过所需溶液的大小\ cite \ cite {quadratic}的大小进行参数时，被发现允许二次内核。在最近的趋势之后，我们首次就输入图的结构参数研究\ textsc {跟踪路径}，该参数是衡量输入图与简单实例的距离。我们证明\ textsc {跟踪路径}允许固定参数可拖动（\ textsc {fpt}）算法当通过顶点盖的大小和群集顶点删除集的大小为输入图进行参数时。
Given a graph $G$ with source and destination vertices $s,t\in V(G)$ respectively, \textsc{Tracking Paths} asks for a minimum set of vertices $T\subseteq V(G)$, such that the sequence of vertices encountered in each simple path from $s$ to $t$ is unique. The problem was proven \textsc{NP}-hard \cite{tr-j} and was found to admit a quadratic kernel when parameterized by the size of the desired solution \cite{quadratic}. Following recent trends, for the first time, we study \textsc{Tracking Paths} with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that \textsc{Tracking Paths} admits fixed-parameter tractable (\textsc{FPT}) algorithms when parameterized by the size of vertex cover, and the size of cluster vertex deletion set for the input graph.
