# P2930: Winner complexity of Node Kayles on subcubic trees

- ID: `P2930`
- Reference: `node-kayles-subcubic-trees`
- Page: https://theoremdb.org/statements/P2930
- Record maturity: Reviewed problem with recorded work

## 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?

### Problem setup

- **Remark.** 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.** A subcubic tree is a finite connected acyclic graph in which every vertex has degree at most three.

### What 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.

## 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. 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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

A complete resolution must satisfy this condition: 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.

### Background and intake notes

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.

- Original intake status: 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.
- The MathOverflow question and every visible answer and comment were checked on 2026-07-27. No polynomial algorithm or PSPACE-hardness proof is supplied for arbitrary maximum-degree-three 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: Paths and several regular-tree families admit explicit analyses, but those subclasses do not determine the complexity on arbitrary subcubic trees.

### Open directions

- **Route 1** (reported): 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](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `node-kayles-subcubic-trees`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>MathOverflow: Complexity of the Node Kayles game in restriction to planar graphs and trees of bounded degree. Question 506760 and every visible answer and comment were checked on 2026-07-27; this record isolates the maximum-degree-three tree case. Question 506760 and every visible answer and comment were checked on 2026-07-27; this record isolates the maximum-degree-three tree case. https://mathoverflow.net/questions/506760/complexity-of-the-node-kayles-game-in-restriction-to-planar-graphs-and-trees-of
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - forum; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>Nuttanon Songsuwan, “Node-Kayles on Trees”. arXiv:2512.24221 (2025). Full preprint relevant to Winner complexity of Node Kayles on subcubic trees. https://arxiv.org/abs/2512.24221
   - preprint; reference source; arXiv:2512.24221, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>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. Full journal article relevant to Winner complexity of Node Kayles on subcubic trees. https://doi.org/10.1016/j.tcs.2014.09.042
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.
4. <a id="reference-4"></a>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. complexity classification for Node Kayles among perfect-information games https://www.sciencedirect.com/science/article/pii/0022000078900454
   - website; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.