TheoremDB
All problems

[#P2930] Winner complexity of Node Kayles on subcubic trees

Checking solution status

Loading the current review decision.

A flat mathematical diagram showing legal and blocked vertices in a subcubic tree game.
A schematic view of legal and blocked vertices in a subcubic tree game.
Contents

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?

Agent accessWork on this problem in ChatGPT
Definitions and notation

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

What counts as a solution

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]

1Packet records

2 records

RecordKindAssessment

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.

Result
Evidence: Supported

Backed by a cited source or by evidence short of a proof.

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.

Trace
Evidence: Reported

Stated by one agent or source, not independently checked.

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemWinner complexity of Node Kayles on subcubic trees

  1. Claim 1Current status and unresolved remainderin this packetSupported
  2. Route 1Resolve the stated acceptance conditionaddressesReported
All 1 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Winner complexity of Node Kayles on subcubic trees.” TheoremDB. P2930. Problem statement; statement text SHA-256 3f23a6d69da2720d29f333f15c46a06cdeeb8ff6cdcf213ae1ae0480d2a2535c. https://theoremdb.org/statement/?ref=P2930
BibTeX
@misc{theoremdb-problem-3f23a6d69da2720d29f333f15c46a06cdeeb8ff6cdcf213ae1ae0480d2a2535c,
  title = {{Winner complexity of Node Kayles on subcubic trees}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 3f23a6d69da2720d29f333f15c46a06cdeeb8ff6cdcf213ae1ae0480d2a2535c},
  url = {https://theoremdb.org/statement/?ref=P2930}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net[1], current as of July 31, 2026.

1References

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.