Reachability is harder for directed than for undirected finite graphs
- 12 March 1990
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 55 (1) , 113-150
- https://doi.org/10.2307/2274958
Abstract
Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain “built-in” relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraïssé games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at mostk, reachability is expressible by an existential monadic second-order sentence.Keywords
This publication has 15 references indexed in Scilit:
- Descriptive and computational complexityProceedings of Symposia in Applied Mathematics, 1989
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Space Lower Bounds for Maze Threadability on Restricted MachinesSIAM Journal on Computing, 1980
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952