Friends-and-strangers is \textsf{PSPACE}-complete

DOI10.1016/J.IPL.2025.106573MaRDI QIDQ6970525zbMATH OpenFDO

Authors Chao Yang, Zhujun Zhang

Publication date 17 June 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2025.106573

zbMATH Keywords

computational complexityfriends-and-strangers graphnondeterministic constraint logicPSPACE-completeness

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• Approximation and hardness of token swapping
• Connectivity of old and new models of friends-and-strangers graphs
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• Friends and strangers walking on graphs
• Graph puzzles, homotopy, and the alternating group
• On the asymmetric generalizations of two extremal questions on friends-and-strangers graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Sliding puzzles and rotating puzzles on graphs
• Swapping colored tokens on graphs
• Swapping labeled tokens on graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The connectedness of the friends-and-strangers graph of a lollipop and others
• Typical and extremal aspects of friends-and-strangers graphs

This page was built for publication: Friends-and-strangers is \textsf{PSPACE}-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970525)