论文标题
关于节点kayles的结构参数化
On Structural Parameterizations of Node Kayles
论文作者
论文摘要
节点凯尔斯（Node Kayles）是图形上众所周知的两人公正游戏：鉴于一个无方向的图，每个播放器交替选择一个不与先前选择的顶点相邻的顶点，而不能选择新顶点的玩家会失去游戏。众所周知，确定第一位玩家是否在此游戏中具有获胜策略的问题是PSPACE完成的问题。关于该问题的算法方面有一些研究。在本文中，我们从固定参数障碍的角度考虑了问题。我们表明，问题是固定参数可通过最小顶点盖的大小或给定图的模块化宽度来参数化的。此外，我们对邻里多样性进行了多项式内核化。
Node Kayles is a well-known two-player impartial game on graphs: Given an undirected graph, each player alternately chooses a vertex not adjacent to previously chosen vertices, and a player who cannot choose a new vertex loses the game. The problem of deciding if the first player has a winning strategy in this game is known to be PSPACE-complete. There are a few studies on algorithmic aspects of this problem. In this paper, we consider the problem from the viewpoint of fixed-parameter tractability. We show that the problem is fixed-parameter tractable parameterized by the size of a minimum vertex cover or the modular-width of a given graph. Moreover, we give a polynomial kernelization with respect to neighborhood diversity.
