[Model] GeneralizedHex

[isPANN]

Motivation

GENERALIZED HEX (P238) from Garey & Johnson, A8 GP1. A PSPACE-complete two-player game on graphs: players alternately claim vertices, and Player 1 wins if a blue path connects two specified terminals s and t. This is the Shannon switching game on vertices, a generalization of the board game Hex to arbitrary graphs. The problem is foundational for establishing PSPACE-completeness of combinatorial games.

Associated rules:

• As target:
  • R182: QBF -> GENERALIZED HEX (Even and Tarjan, 1976; establishes PSPACE-completeness)
• As source: (none found in current issue set)

Definition

Name: GeneralizedHex

Reference: Garey & Johnson, Computers and Intractability, A8 GP1

Mathematical definition:

INSTANCE: Graph G = (V,E) and two specified vertices s,t ∈ V.
QUESTION: Does player 1 have a forced win in the following game played on G? The players alternate choosing a vertex from V−{s,t}, with those chosen by player 1 being colored "blue" and those chosen by player 2 being colored "red." Play continues until all such vertices have been colored, and player 1 wins if and only if there is a path from s to t in G that passes through only blue vertices.

Variables

• Count: n - 2 = |V| - 2 (one variable per non-terminal vertex; s and t are fixed)
• Per-variable domain: {0, 1} — 0 = red (Player 2 claimed), 1 = blue (Player 1 claimed)
• Meaning: color(v) in {0, 1} for each v in V \ {s, t}. The assignment represents the final coloring of the board. Player 1 wins iff there exists an s-t path using only vertices with color = 1 (blue). The game dynamics determine which colorings are reachable under optimal play.

Schema (data type)

Type name: GeneralizedHex
Variants: none (operates on a general undirected graph with two distinguished vertices)

Field	Type	Description
num_vertices	usize	Number of vertices n = |V|
edges	Vec<(usize, usize)>	Undirected edges {u, v} in E
source	usize	Index of the source terminal vertex s
target	usize	Index of the target terminal vertex t

Complexity

• Best known exact algorithm: Exhaustive game-tree search via minimax with alpha-beta pruning. The game tree has depth |V| - 2 and branching factor up to |V| - 2 at each level, giving worst-case O((n-2)!) time. With memoization of game states, the state space is 3^(n-2) (each non-terminal vertex is unclaimed, blue, or red), yielding O(3^n) time and space. The problem is PSPACE-complete (Even and Tarjan, 1976), so no polynomial-time algorithm is expected. The Shannon switching game on edges (a variant) is solvable in polynomial time via matroid theory (Bruno and Weinberg, 1970).

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E) and two specified vertices s,t ∈ V.
QUESTION: Does player 1 have a forced win in the following game played on G? The players alternate choosing a vertex from V−{s,t}, with those chosen by player 1 being colored "blue" and those chosen by player 2 being colored "red." Play continues until all such vertices have been colored, and player 1 wins if and only if there is a path from s to t in G that passes through only blue vertices.

Reference: [Even and Tarjan, 1976]. Transformation from QBF.
Comment: PSPACE-complete. The variant in which players alternate choosing an edge instead of a vertex, known as "the Shannon switching game on edges," can be solved in polynomial time [Bruno and Weinberg, 1970]. If G is a directed graph and player 1 wants a "blue" directed path from s to t, both the vertex selection game and the arc selection game are PSPACE-complete [Even and Tarjan, 1976].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible game plays via minimax; each state is a partial coloring of V \ {s,t}. Check s-t blue connectivity at terminal states.)
• It can be solved by reducing to integer programming.
• Other: Alpha-beta pruning with transposition table for practical speedup; retrograde analysis for small instances.

Example Instance

Input:
G = (V, E) with V = {0, 1, 2, 3, 4, 5, 6, 7}, s = 0, t = 7
Edges: {0,1}, {0,2}, {1,3}, {1,4}, {2,3}, {2,5}, {3,6}, {4,6}, {5,6}, {6,7}

This graph has 8 vertices and 10 edges. Players color vertices 1-6 (6 non-terminal vertices).

Game analysis:
Player 1 needs a blue path from vertex 0 to vertex 7. Vertex 6 is the only vertex adjacent to 7, so Player 1 must claim vertex 6.

Possible s-t paths through the graph:

• 0 -> 1 -> 3 -> 6 -> 7
• 0 -> 1 -> 4 -> 6 -> 7
• 0 -> 2 -> 3 -> 6 -> 7
• 0 -> 2 -> 5 -> 6 -> 7

Player 1 strategy: Claim vertex 6 first (critical bottleneck). Then Player 2 claims some vertex, say 3. Player 1 claims vertex 1. Player 2 claims vertex 5. Player 1 claims vertex 4. Player 2 claims vertex 2.
Blue vertices: {6, 1, 4}. Blue path: 0 -> 1 -> 4 -> 6 -> 7. Player 1 wins!

Alternatively, Player 2 may try to block: After Player 1 takes 6, Player 2 takes 1. Player 1 takes 2. Player 2 takes 3. Player 1 takes 5. Player 2 takes 4.
Blue vertices: {6, 2, 5}. Blue path: 0 -> 2 -> 5 -> 6 -> 7. Player 1 still wins!

Since vertex 6 is the only gateway to t = 7, and Player 1 goes first, Player 1 can always secure vertex 6 and then find a blue path through at least one of the two vertex-disjoint sub-paths (via {1,3}/{1,4} or {2,3}/{2,5}).

Answer: YES -- Player 1 has a forced win.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; foundational PSPACE-complete game problem
Non-trivial	✅ Pass	Two-player game semantics are fundamentally distinct from all existing problems
Correctness	✅ Pass	All references verified (Even & Tarjan 1976, Bruno & Weinberg 1970)
Well-written	⚠️ Warn	Schema should use graph type pattern; variable domain inconsistency; evaluate() semantics unclear

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

GeneralizedHex does not exist in the codebase. The problem is the canonical PSPACE-complete two-player game, foundational for establishing PSPACE-completeness of combinatorial games. It has one planned incoming reduction (QBF -> GeneralizedHex). While only one reduction is listed, this is appropriate for a game problem that serves primarily as a reduction target from QBF. The problem fills a genuine gap — no two-player game problems currently exist in the reduction graph.

Non-trivial

GeneralizedHex is genuinely distinct from all existing problems. It is a two-player alternating game on a graph with connectivity-based winning condition. No existing problem in the codebase involves adversarial game-tree semantics. This is not a variant, restriction, or renaming of any existing problem.

Correctness

References verified:

• Even & Tarjan (1976): Confirmed. "A Combinatorial Problem Which Is Complete in Polynomial Space" — published in Journal of the ACM, Vol. 23, No. 4, pp. 710-719, October 1976. Establishes PSPACE-completeness of the generalized Hex (Shannon switching game on vertices) via reduction from QBF.
• Bruno & Weinberg (1970): Confirmed. "A Constructive Graph Theoretic Solution of the Shannon Switching Game" — published in IEEE Transactions on Circuit Theory, Vol. CT-17, No. 1, 1970, pp. 74-81. Shows the edge-selection variant is solvable in polynomial time using matroid theory.
• Garey & Johnson A8 GP1 reference: Consistent with the book's Games and Puzzles section.

Complexity claim: The O(3^n) bound via memoization is reasonable — each non-terminal vertex has 3 states (unclaimed, blue, red), so the state space is at most 3^(n-2). The (n-2)! game-tree bound without memoization is also correct. No better exact algorithms were found in the literature for the general case.

Well-written

Strengths:

• Mathematical definition is clear and matches Garey & Johnson verbatim
• Example is well-constructed (8 vertices, 10 edges) with two different Player 2 response strategies analyzed
• The distinction between vertex and edge versions of the Shannon switching game is correctly noted

Issues to address:

1. Schema should use graph type pattern: The project stores graph problems using typed graph structures (e.g., SimpleGraph), not raw Vec<(usize, usize)>. The schema should follow the existing pattern with a graph type parameter G, similar to other graph problems. The source and target terminal vertices would be additional fields beyond the graph. Look at existing graph problems like MaximumIndependentSet or MaxCut for the pattern.

2. Variable domain inconsistency: The Variables section states domain {0, 1} (binary: red/blue for the final coloring), but the Complexity section uses 3^(n-2) states (unclaimed/blue/red for game-tree search). These represent different views: the final coloring vs. intermediate game states. For the Problem trait, the dims() method returns the per-variable domain. If dims() returns [2; n-2] (binary), then evaluate() receives a complete assignment of all non-terminal vertices to blue/red, and there are 2^(n-2) configurations to enumerate — not 3^(n-2). The issue should clarify which representation is intended and ensure consistency.

3. evaluate() semantics need clarification: This is the same fundamental design challenge as QBF ([Model] QuantifiedBooleanFormulas(qbf)(*) #571). The Problem trait's evaluate(config: &[usize]) receives a single complete configuration. For a two-player game:

   • Option A: Treat each config as a final coloring (all vertices assigned blue/red). evaluate() returns true if there exists an s-t path through blue vertices. This loses the game-tree/alternation semantics — brute force would enumerate all 2^(n-2) colorings and check s-t connectivity, but would not determine who wins under optimal play.
   • Option B: Implement game-tree evaluation outside the evaluate() method. The evaluate() method checks a specific coloring, but the "does Player 1 have a forced win?" question requires minimax search over the game tree.

   The issue should explicitly state which approach is intended. Option A is simpler and consistent with the SatisfactionProblem trait, but it changes the problem semantics (checking a specific coloring vs. determining optimal play outcome).

4. num_vertices field is redundant if using a graph type — it would be derivable from the graph structure.

Recommendations

• Align the schema with the project's graph type pattern (see src/models/graph/max_cut.rs for a graph problem without weights)
• Clarify the evaluate() semantics and dims() return value in the issue
• For declare_variants!, a complexity string of "3^num_vertices" or "2^num_vertices" would be needed depending on the chosen representation
• Consider whether QBF ([Model] QuantifiedBooleanFormulas(qbf)(*) #571) should be implemented first, since it is a prerequisite for the QBF -> GeneralizedHex reduction