About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
Reachability is harder for directed than for undirected finite graphs
Abstract
It is shown that for directed graphs, reachability can not be expressed by an existential monadic second-order sentence. The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic. However, it is shown that for directed graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence. One reason for the interest in the main result is that while there is considerable empirical evidence (in terms of the efficiency of algorithms that have been discovered) that reachability in directed graphs is 'harder' than reachability in unidirected graphs, this is the first proof in a precise technical sense that this is so.