Winner determination algorithms for graph games with matching structures

DOI10.1007/S00453-023-01136-WMaRDI QIDQ6119832zbMATH OpenFDO

Authors Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

Publication date 25 March 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.05307

zbMATH Keywords

vertex coverneighborhood diversitycombinatorial game theoryexact exponential-time algorithm\textsc{Arc Kayles}

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Abstract: Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in $O^{\ast }(2^n)$ time by a simple algorithm, where $n$ is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time $O^{\ast }(1.4143^{a{u}^2+3.17au})$, $O^{\ast }(1.3161^{a{u}^2+4au})$, and $O^{\ast }(1.1893^{a{u}^2+6.34au})$, respectively, where $au$ is the vertex cover number. Furthermore, we present an $O^{\ast }((n/u+1{)}^u)$-time algorithm for Arc Kayles, where $u$ is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in $O^{\ast }(2^{n/2})(=O(1.4143^n))$ time, which improves $O^{\ast }(3^{n/3})(=O(1.4423^n))$ by a direct adjustment of the analysis of Bodlaender et al.'s $O^{\ast }(3^{n/3})$-time algorithm for Node Kayles.

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Exact algorithms for Kayles
• Improved upper bounds for vertex cover
• Kayles and Nimbers
• New results for Domineering from combinatorial game theory endgame databases
• On structural parameterizations of Node Kayles
• On the complexity of some two-person perfect-information games
• Polynomial time graph families for Arc Kayles
• Solving \(8\times 8\) Domineering
• The computational complexity of the game of Set and its theoretical applications
• Winner determination algorithms for graph games with matching structures
• \(11\times 11\) Domineering is solved: the first player wins

This page was built for publication: Winner determination algorithms for graph games with matching structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6119832)