Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-047 | 10th November 1999 00:00

Graph Ramsey games

RSS-Feed

Abstract:

We consider combinatorial avoidance and achievement games
based on graph Ramsey theory: The players take turns in coloring
still uncolored edges of a graph G, each player being assigned a
distinct color, choosing one edge per move. In avoidance games,
completing a monochromatic subgraph isomorphic to another graph A
leads to immediate defeat or is forbidden and the first player that
cannot move loses. In the avoidance+ variants, both players are free
to choose more than one edge per move. In achievement games, the first
player that completes a monochromatic subgraph isomorphic to A
wins. Erdos & Selfridge (1973) were the first to identify some
tractable subcases of these games, followed by a large number of
further studies. We complete these investigations by settling the
complexity of all unrestricted cases: We prove that general graph
Ramsey avoidance, avoidance+, and achievement games and several
variants thereof are PSPACE-complete. We ultra-strongly solve some
nontrivial instances of graph Ramsey avoidance games that are based on
symmetric binary Ramsey numbers and provide strong evidence that all
other cases based on symmetric binary Ramsey numbers are effectively
intractable.



ISSN 1433-8092 | Imprint