论文标题
参数化的时间探索问题
Parameterized temporal exploration problems
论文作者
论文摘要
在本文中，我们研究了确定给定时间图的问题的固定参数障碍性是访问所有顶点（时间探索）还是在某些问题变体中的某些子集的时间表。正式地，时间图是v（g_t）= v（g）的序列<g_1，...，g_l>，对于[l]中的所有t和一些基础图g，e（g_t）e（g_t）的E（g_t）子集，而时间段的步行是一个时间值得探测的边缘traveraversals的序列。我们考虑了严格的变体，其中边缘必须在严格增加的时间步中遍历，而非图案变体必须在每个时间步中遍历任意数量的边缘。对于这两个变体，我们给出了fpt算法，以解决访问给定的X的暂时步行的问题，该步行X的X x |由| X |参数化，以及找到一个时间步行的问题，该问题至少访问k（g）中的k个不同的顶点，由k参数化。我们还显示了两个变体的时间探索问题的固定版本的W [2]。对于非图案变体，我们给出了通过输入图的寿命来参数的时间探索问题的FPT算法，如果每个时间段中的每个时间段中的图具有最多两个连接的组件，则可以在多项式时间内解决时间探索问题。
In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence <G_1,...,G_L> of graphs with V(G_t) = V(G) and E(G_t) a subset of E(G) for all t in [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. We consider both the strict variant, in which edges must be traversed in strictly increasing timesteps, and the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V(G), parameterized by k. We also show W[2]-hardness for a set version of the temporal exploration problem for both variants. For the non-strict variant, we give an FPT algorithm for the temporal exploration problem parameterized by the lifetime of the input graph, and we show that the temporal exploration problem can be solved in polynomial time if the graph in each timestep has at most two connected components.
