Cover Image

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Burke, Kyle, Cashman, Caroline, Davies, Alfie, Yoshiwatari, Kanae, Yu, Francesca
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics Combinatorics 91A46 F.1.3; G.2.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

Battle Sheep is PSPACE-complete
by: Burke, Kyle, et al.
Published: (2025)

Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
by: Burke, Kyle, et al.
Published: (2024)

Mind the gap: A real-valued distance on combinatorial games
by: Burke, Kyle, et al.
Published: (2026)

Multiplicative Modular Nim (MuM)
by: Tyagi, Satyam
Published: (2025)

Paintbucket on graphs is PSPACE-complete
by: Saunders, Ethan J., et al.
Published: (2024)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
by: Ulfarsson, Henning
Published: (2026)

Maker-Maker games of rank 4 are PSPACE-complete
by: Galliot, Florian, et al.
Published: (2025)

Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete
by: Koepke, Finn Orson
Published: (2025)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
by: Galliot, Florian
Published: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
by: Burke, Kyle, et al.
Published: (2024)

Misère Cricket Pitch
by: Nowakowski, Richard J., et al.
Published: (2024)

Complexity of Maker-Breaker Games on Edge Sets of Graphs
by: Duchêne, Eric, et al.
Published: (2023)

A generalization of Arc-Kayles
by: Dailly, Antoine, et al.
Published: (2017)

A convergence technique for the game i-Mark
by: Nivasch, Gabriel, et al.
Published: (2025)

Additive sink subtraction
by: Bhagat, Anjali, et al.
Published: (2026)

Node-Kayles on Trees
by: Songsuwan, Nuttanon
Published: (2025)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Impartial Chess on Integer Partitions
by: Gottlieb, Eric, et al.
Published: (2025)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
by: Concha-Vega, Pablo
Published: (2026)

Coin Turning Games on Partially Ordered Sets
by: Ishikawa, Masao, et al.
Published: (2026)

Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
by: Könen, David, et al.
Published: (2023)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

Dyck Paths Enumerated by the Q-bonacci Numbers
by: Barcucci, Elena, et al.
Published: (2024)

On The Roots of Independence Polynomial: Quantifying The Gap
by: Prakash, Om, et al.
Published: (2025)

A Bijection between Stacked Directed Polyominoes and Motzkin Paths with Alternative Catastrophes
by: Schager, Florian, et al.
Published: (2024)

Binary Words Containing Few Abelian Squares
by: Fazekas, Szilard Zsolt, et al.
Published: (2026)

The Converse of the Real Orthogonal Holant Theorem
by: Young, Ben
Published: (2024)

The Most Malicious Maître D'
by: Madhavarapu, Tejo V.
Published: (2024)

Trail Trap: a variant of Partizan Edge Geography
by: Buchanan, Calum, et al.
Published: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Graph Irregularity via Edge Deletions
by: Bensmail, Julien, et al.
Published: (2025)

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Computational Aspects of Cores of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)