论文标题
在腰围的图表上滑动的令牌滑动五
Token sliding on graphs of girth five
论文作者
论文摘要
在令牌滑动问题中，我们给了一个图形$ g $和两个独立的集合$ i_s $和$ i_t $ in $ g $的$ k $ k \ geq 1 $。目的是确定是否存在序列$ \ langle I_1，i_2，i_2，\ ldots，i_ \ ell \ rangle \ rangle $的独立集合，使得所有$ i \ in \ {1，\ ldots，\ el \ ell \ ell \} $ i_i \ triangle i_ {i + 1} = \ {u，v \} \在e（g）$中。直观地，我们将每个独立集视为放置在图形顶点上的代币集合。然后，问题询问是否存在一系列独立集，将$ i_s $转换为$ i_t $，在每个步骤中，我们都可以将一个令牌从顶点滑到相邻的顶点。在本文中，我们专注于由$ k $参数化的令牌滑动的参数化复杂性。如Bartier等人所示，问题是W [1] - 围栏图四个或更少的图表，作者提出了一个问题，即是否存在常数$ p \ geq 5 $，以使该问题在围栏图上至少可以在至少$ p $的图表上进行固定参数。我们积极回答他们的问题，并证明该问题确实是固定参数在围栏五个以上的图表上固定的，该参数可以根据输入图的围墙来确定由代币数量的代币滑动参数的完全分类。
In the Token Sliding problem we are given a graph $G$ and two independent sets $I_s$ and $I_t$ in $G$ of size $k \geq 1$. The goal is to decide whether there exists a sequence $\langle I_1, I_2, \ldots, I_\ell \rangle$ of independent sets such that for all $i \in \{1,\ldots, \ell\}$ the set $I_i$ is an independent set of size $k$, $I_1 = I_s$, $I_\ell = I_t$ and $I_i \triangle I_{i + 1} = \{u, v\} \in E(G)$. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms $I_s$ into $I_t$ where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by $k$. As shown by Bartier et al., the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant $p \geq 5$ such that the problem becomes fixed-parameter tractable on graphs of girth at least $p$. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.
