Linear-Time Algorithms for Deterministic Graphical Games

Definitions and mathematical statement

A finite-state deterministic graphical game of perfect information is described by a finite directed graph $G=(V,E)$, together with additional game data. Vertices represent states, edges represent permitted transitions, and all players observe the current state and the preceding play. Determinism means that a selected move determines its successor state, without a random transition. The supplied record does not specify the number of players, who chooses moves at each state, the outcomes or payoffs, or how finite and infinite plays are evaluated.

Source question. Can finite-state deterministic graphical games of perfect information, given explicitly as graphs, be solved in linear time by a comparison-based algorithm?

The intended algorithmic quantifiers are whether there exists a single comparison-based algorithm that correctly solves every explicitly represented game in the intended class, using time linear in the relevant input size. However, the supplied record does not define the required output of "solving" a game, the permitted comparisons, or the input-size and operation-cost conventions. Consequently, this question cannot yet be made into a fully specified algorithmic proposition. In particular, a bound of $O(|V|+|E|)$ requires conventions about the representation and cost of any additional game data; those conventions are not supplied. Terminal states, states with no outgoing edges, cycles, and infinite plays also require explicit treatment before the intended class and correctness criterion are determined.

Short English statement

The question asks for one comparison-based algorithm that solves every finite deterministic perfect-information game supplied as an explicit graph in linear time. The record leaves the game objectives, required solution, treatment of infinite play, and computational cost model unspecified, so the precise algorithmic target requires clarification from the cited source.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001247$, title: Linear-Time Algorithms for Deterministic Graphical Games; exact source problem code: catalogue entry. The record gives proposed year 2009 and supplies no individual proposer attribution.
• Supplied report citation: Combinatorics and Probability (2009), Oberwolfach Reports, pp. 1225--1302, DOI: 10.4171/owr/2009/23. https://doi.org/10.4171/owr/2009/23. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference, "Oberwolfach Report 23, Combinatorics and Probability": https://doi.org/10.4171/owr/2009/23.
• Supplied literature reference, "Deterministic graphical games revisited": https://doi.org/10.1007/978-3-540-69407-6_1.
• Supplied literature reference, "original open-problem statement": https://doi.org/10.4171/owr/2009/23.
• Literature checked at: 2026-08-21. This is supplied dated curation, not independently verified. The supplied assessment labels the problem open and states that the linear-time comparison-based question was explicitly left open, while later algorithms improve special cases without establishing the general bound. The background qualifies this assessment as dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement "exact" and reports a manual review finding the extracted statement self-contained, mathematically coherent, and free of LaTeX or report-layout artifacts. These are supplied verification claims, not independent verification in this draft.