Source-linked AI summary
It's Hard to PArcK
Kyle Burke, Jeffrey Leman, Craig Tennenhouse
TL;DR
The paper addresses the computational complexity of Partizan Arc Kayles, a graph generalization of Domineering. It reduces Positive CNF to PArcK using variable and clause gadgets, establishing PSPACE-completeness even without green edges. This improves on the prior NP-hardness result while leaving the complexity of Domineering and impartial Arc Kayles open.
Problem
The computational complexity of PArcK was previously known only through an NP-hardness result, motivating a stronger intractability result for this ruleset.
Method
The paper reduces Positive CNF to PArcK using variable and clause gadgets, with variable gadgets acting as ±1 switches and the construction using red and blue edges.
Results
PArcK is PSPACE-complete, including on positions without any green edges.
Takeaways & Limitations
The result strengthens PArcK’s known hardness and connects its complexity to longstanding questions about Domineering and impartial Arc Kayles.
Takeaways & Limitations
The computational complexities of Domineering and impartial Arc Kayles remain open problems.
Abstract
from arXiv · showhide
We show that Partizan Arc Kayles (PArcK), a generalization of Domineering to graphs, is PSPACE-complete via a reduction from Positive CNF and with recently-discovered techniques for creating PArcK positions with high temperature. The reduction uses only red and blue edges.
1 Introduction
Partizan Arc Kayles (PArcK) is a partizan normal-play graph game and a generalization of Domineering. The paper places PArcK within Algorithmic Combinatorial Game Theory and develops its analysis using standard game values.
- Game setting: Under Normal Play, the player with no available move at the beginning of their turn loses.The last player to move wins.
- Partizan Arc Kayles: PArcK is played on simple graphs with blue, red, and green edges; Left may remove blue or green edges, while Right may remove red or green edges.Removing an edge also removes its incident vertices and every edge incident to those vertices.
- Relation to Domineering: PArcK generalizes Domineering, which is recovered on a grid by making vertical edges blue and horizontal edges red.In Domineering, Left places vertical dominoes and Right places horizontal dominoes.
- Game values: Normal-play positions can be analyzed with game values and combined through the disjunctive sum when a game decomposes into independent pieces.The introduction highlights zero, positive, negative, and ∗ positions as values of interest.
- Algorithmic Combinatorial Game Theory: Algorithmic Combinatorial Game Theory studies algorithmic solutions and computational intractability for specific combinatorial-game rulesets.The paper presents an intractability result for PArcK, improving an earlier NP-hardness result.
2 Values of Positions
This section develops reusable PArcK positions and evaluates their game values, including the variable gadget −A2, paths, extensions, and a lemma bounding a pendant-red-edge construction.
- Basic positions: The section introduces basic PArcK positions with values 1, −1, and ∗ as building blocks for later constructions.These positions are shown as the basic values used in the section.
- Variable gadget: The variable gadget −A2 has value 0, but choosing an edge incident to m removes two red edges and gives value 2.The vertex m connects the gadget to other parts of the graph.
- Path gadgets: The 3-edge path has value −1/2 ± 1/2, and adding a blue tail preserves that value.The added-tail position is evaluated as { 0, −1 | −1, ∗} = { 0 | −1 } = −1/2 ± 1/2.
- Path gadgets: The 4-edge path has value −1∗, and adding a blue tail preserves that value.The original path gives Left only a move to −1, while Right can move to −1 or ∗.
- Path gadgets: The 6-edge path has value −1, and adding one or two blue-tail extensions leaves the value unchanged.The derivations reduce the extended positions to forms with value −1.
- Additional gadgets: Further modifications of −A2 yield values 0, −1/2 ± 1/2, −3/2 ± 1/2, and −2∗ for gadgets used later.These include a reverse −A2, an edge merge, a red middle edge, and a two-edge path.
- Death Star Lemma: The Death Star Lemma states that adding a vertex connected by blue edges and bearing a pendant red edge produces G′ ≥ G −1.The proof handles the cases of no added blue edges and Right’s possible moves by induction.
3 PSPACE Reduction
The reduction from Positive CNF uses variable and clause gadgets to encode truth assignments in PArcK, forcing play through variable choices before clause outcomes determine the winner. The construction establishes PSPACE-completeness.
- Reduction setup: The reduction assumes an odd number of variables and more than one clause, adding an unused variable or cloning a solitary clause when necessary.
- Variable gadgets: Variable gadgets act as ±1 switches: choosing T or F changes the value of the −A2 component and removes connected red edges.The gadget is designed so that Left choosing T leaves value 1, while Right choosing F leaves value −1.
- Clause analysis: After all variables are claimed and the master edges are absent, the remaining graph has value 0, regardless of which clauses remain connected to variables.
- Clause analysis: For clause gadgets, the value is −1 when there are multiple clauses and all clause-variable connections satisfy the required condition, while a single clause has value −1/2 ± 1/2∗.The connected clause analysis is captured by Theorem 3.3, whose induction treats the one-clause case separately.
- Clause analysis: If at least one clause loses all connections to variable nodes, its value becomes strictly less than −1, distinguishing a false Positive CNF assignment from a true one.Right can choose the corresponding edge sj, leaving an extra value of −2 in that clause and making the total position winning for Right.
- Variable gadgets: Players are always motivated to play on variable gadgets until every variable has been claimed.This ensures the game first records a complete True/False assignment before clause gadgets determine the remaining value.
- Hardness result: The reduction preserves the winner: Left wins the constructed PArcK position exactly when True wins the Positive CNF instance.Consequently, PArcK is PSPACE-complete.
4 Conclusions and Future Work
The paper proves that PArcK is PSPACE-complete even without green edges, improving a prior NP-hardness result. It also identifies unresolved complexity questions for Domineering and impartial Arc Kayles.
- PArcK is PSPACE-complete even on positions without any green edges.
- This result improves the earlier NP-hardness result for PArcK.
- Future work: The computational complexity of Domineering remains an open problem.
- Future work: The computational complexity of impartial Arc Kayles remains an open problem.Arc Kayles differs from PArcK by having all edges green.