Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-092 | 2nd October 2001 00:00

A Note on the Complexity of the Reachability Problem for Tournaments

RSS-Feed




TR01-092
Authors: Till Tantau
Publication: 30th November 2001 14:50
Downloads: 4262
Keywords: 


Abstract:

Deciding whether a vertex in a graph is reachable from another
vertex has been studied intensively in complexity theory and is
well understood. For common types of graphs like directed graphs,
undirected graphs, dags or trees it takes a (possibly
nondeterministic) logspace machine to decide the reachability
problem, and the succinct versions of these problems (which often
arise in hardware design) are all PSPACE-complete. In this
paper we study tournaments, which are directed graphs with exactly
one edge between any two vertices. We show that the tournament
reachability problem is first order definable and that its
succinct version is \Pi_2^P-complete.



ISSN 1433-8092 | Imprint