Faster Winner Determination Algorithms for (Colored) Arc Kayles

Arc Kayles and Colored Arc Kayles, two-player games on a graph, are generalized versions of well-studied combinatorial games Cram and Domineering, respectively. In Arc Kayles, players alternately choose an edge to remove with its adjacent edges, and the player who cannot move is the loser. Colored Arc Kayles is similarly played on a graph with edges colored in black, white, or gray, while the black (resp., white) player can choose only a gray or black (resp., white) edge. For Arc Kayles, the vertex cover number (i.e., the minimum size of a vertex cover) is an essential invariant because it is known that twice the vertex cover number upper bounds the number of turns of Arc Kayles, and for the winner determination of (Colored) Arc Kayles, 2^O(τ2)n^O(1)-time algorithms are known, where τ is the vertex cover number and n is the number of vertices. In this paper, we first give a polynomial kernel for Colored Arc Kayles parameterized by τ, which leads to a faster 2^O(τlogτ)n^O(1)-time algorithm for Colored Arc Kayles. We then focus on Arc Kayles on trees, and propose a 2.2361^τn^O(1)-time algorithm. Furthermore, we show that the winner determination Arc Kayles on a tree can be solved in O(1.3831ⁿ) time, which improves the best-known running time O(1.4143ⁿ). Finally, we show that Colored Arc Kayles is NP-hard, the first hardness result in the family of the above games.