[#P2930] Winner complexity of Node Kayles on subcubic trees
Problem. Given a finite tree \(T\) of maximum degree at most three as a Node Kayles position, what is the complexity of deciding whether the next player has a winning strategy? In particular, is the problem polynomial-time solvable or PSPACE-complete?
1Context
Tree decompositions, canonical rooted-subtree states, and bounded-degree game gadgets are reusable. The unresolved point is whether the game requires unbounded information across a separator even when the graph is a tree.
2Problem setup
Definition 1 (A move chooses a remaining vertex and deletes that vertex together with all of its remaining neighbors; players alternate and the player making the last legal move wins). A move chooses a remaining vertex and deletes that vertex together with all of its remaining neighbors; players alternate and the player making the last legal move wins.
Definition 2 (A subcubic tree). A subcubic tree is a finite connected acyclic graph in which every vertex has degree at most three.
Remark 1. Tree decompositions, canonical rooted-subtree states, and bounded-degree game gadgets are reusable. The unresolved point is whether the game requires unbounded information across a separator even when the graph is a tree.
3What counts as a solution
- Give a deterministic polynomial-time winner algorithm for all subcubic trees with proof of its running time and correctness, or give a polynomial-time reduction proving PSPACE-hardness together with the standard PSPACE membership argument.
- A hardness construction must output a connected acyclic graph of maximum degree at most three and preserve the winner under normal play.
1Status
Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees. Give a deterministic polynomial-time winner algorithm for all subcubic trees with proof of its running time and correctness, or give a polynomial-time reduction proving PSPACE-hardness together with the standard PSPACE membership argument.[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-31. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.
- The tree algorithm in Theoretical Computer Science 2014 was checked. Its O(1.4423^n) running time is exponential and therefore does not settle membership in P.
- ArXiv:2512.24221 was checked for recent Node Kayles results on regular trees and joined constructions. Those structured families do not include all finite subcubic trees.
- Schaefer's general PSPACE-completeness result and a local TheoremDB search were checked for bounded-degree tree gadgets; no direct classification or duplicate was found.
Recorded example 1. Paths and several regular-tree families admit explicit analyses, but those subclasses do not determine the complexity on arbitrary subcubic trees.
How the 2 records connect
ProblemWinner complexity of Node Kayles on subcubic trees
2See also
- Gathering the frog game at the root of a full binary treecombinatorial games
- Complexity of equality for binary-code weight enumeratorscomputational complexity
- Unique Games conjecturecomputational complexity
How to cite
TheoremDB contributors, “Winner complexity of Node Kayles on subcubic trees,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/node-kayles-subcubic-treesThis page as plain text: node-kayles-subcubic-trees.md
This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net[1], current as of July 31, 2026.
1References
- Packet source. MathOverflow: Complexity of the Node Kayles game in restriction to planar graphs and trees of bounded degree, source checked for the TheoremDB status review (2026-07-31). Question 506760 and every visible answer and comment were checked on 2026-07-27; this record isolates the maximum-degree-three tree case. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Winner complexity of Node Kayles on subcubic trees: UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.Source named by the research packet.
- MathOverflow: Complexity of the Node Kayles game in restriction to planar graphs and trees of bounded degree, source checked for the TheoremDB status review (2026-07-31). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:2512.24221, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.Also cited at Full preprint relevant to Winner complexity of Node Kayles on subcubic trees.Source used to assess the problem's recorded status.For Winner complexity of Node Kayles on subcubic trees: UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.
- Hans L. Bodlaender, Dieter Kratsch, and Sjoerd T. Timmer, “Exact algorithms for Kayles”. Theoretical Computer Science 562 (2015), 165-176. DOI 10.1016/j.tcs.2014.09.042. Status evidence identified in the source record and checked at the linked publication. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.Also cited at Full journal article relevant to Winner complexity of Node Kayles on subcubic trees.Source used to assess the problem's recorded status.For Winner complexity of Node Kayles on subcubic trees: UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.
- Thomas J. Schaefer, “On the Complexity of Some Two-Person Perfect-Information Games,” Journal of Computer and System Sciences 16(2) (1978), 185-225. DOI 10.1016/0022-0000(78)90045-4. Status evidence identified in the source record and checked at the linked publication. ↗journal article · primary source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. General Node Kayles is PSPACE-complete, and exact exponential algorithms are known on trees. The checked recent work on regular-tree families does not classify arbitrary subcubic trees.Also cited at complexity classification for Node Kayles among perfect-information games.Source used to assess the problem's recorded status.For Winner complexity of Node Kayles on subcubic trees, this source establishes the general PSPACE-completeness baseline without classifying Node Kayles on arbitrary subcubic trees.
An original CC0 reformulation motivated by the cited MathOverflow complexity question; the subcubic-tree target is stated independently.