Reachability is harder for directed than for undirected finite graphs.

*(English)*Zbl 0708.03016A directed (undirected) graph is (s,t)-connected if there is a directed (undirected) path from s to t. Refer to the problem of deciding whether a given directed (undirected) graph with two given points s and t is (s,t)- connected as the directed (undirected) reachability problem. P. Kanellakis observed that undirected reachability is monadic \(\Sigma^ 1_ 1\) and posed as an open problem the question of whether directed reachability is monadic \(\Sigma^ 1_ 1\). The main result in this paper is that directed reachability is not monadic \(\Sigma^ 1_ 1\) (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. In addition, this paper proves that for directed finite graphs with degree at most k, reachability is monadic \(\Sigma^ 1_ 1\).

Reviewer: Tao Renji

##### MSC:

03D15 | Complexity of computation (including implicit computational complexity) |

05C40 | Connectivity |

68Q25 | Analysis of algorithms and problem complexity |

68R10 | Graph theory (including graph drawing) in computer science |

##### Keywords:

existential monadic second-order sentence; reachability problem; undirected reachability; Ehrenfeucht-Fraïssé games
PDF
BibTeX
XML
Cite

\textit{M. Ajtai} and \textit{R. Fagin}, J. Symb. Log. 55, No. 1, 113--150 (1990; Zbl 0708.03016)

Full Text:
DOI

##### References:

[1] | Proceedings of the Sixth ACM Symposium on Principles of Database Systems pp 214– (1987) |

[2] | DOI: 10.1214/aoms/1177729330 · Zbl 0048.11804 |

[3] | DOI: 10.1002/malq.19870330107 · Zbl 0652.03032 |

[4] | Proceedings of the Twentieth IEEE Symposium on Foundations of Computer Science pp 218– (1979) |

[5] | Proceedings of the Seventeenth ACM Symposium on Theory of Computing pp 143– (1985) |

[6] | DOI: 10.1016/0168-0072(83)90038-6 · Zbl 0519.03021 |

[7] | Mathematical Systems Theory 15 pp 127– (1982) |

[8] | Proceedings of the Nineteenth ACM Symposium on Theory of Computing pp 325– (1987) |

[9] | Proceedings of the Twenty-sixth IEEE Symposium on Foundations of Computer Science pp 464– (1985) |

[10] | Proceedings of the Second IEEE Conferencee on Structure in Complexity Theory pp 203– (1987) |

[11] | Publications Scientifiques de l’Université d’Alger 1 pp 35– (1954) |

[12] | DOI: 10.1002/malq.19750210112 · Zbl 0317.02054 |

[13] | Complexity of computation 7 pp 43– (1974) |

[14] | Fundamenta Mathematicae 49 pp 129– (1961) |

[15] | Proceedings of the Nineteenth ACM Symposium on Theory of Computing pp 1– (1987) |

[16] | DOI: 10.1137/0209048 · Zbl 0445.68038 |

[17] | DOI: 10.1016/0022-0000(82)90012-5 · Zbl 0511.68073 |

[18] | Proceedings of the Nineteenth ACM Symposium on Theory of Computing pp 425– (1987) |

[19] | Proceedings of the Twentieth ACM Symposium on Theory of Computing pp 539– (1988) |

[20] | Foundations of deductive databases and logic programming (1988) · Zbl 0726.68064 |

[21] | DOI: 10.1090/psapm/038/1020810 |

[22] | DOI: 10.1137/0216051 · Zbl 0634.68034 |

[23] | DOI: 10.1016/S0019-9958(86)80029-8 · Zbl 0612.68086 |

[24] | Parallel Graph Algorithms (1987) |

[25] | Computers and intractibility: a guide to the theory of NP-completeness (1979) |

[26] | Proceedings of the Third Conference on Structure in Complexity Theory pp 116– (1988) |

[27] | Handbook of Theoretical Computer Science |

[28] | Random graphs (1982) |

[29] | Proceedings of the Fourteenth ACM Symposium on Theory of Computing pp 137– (1982) |

[30] | Proceedings of the Twenty-fourth IEEE Symposium on Foundations of Computer Science pp 304– (1983) |

[31] | Proceedings of the Sixth ACM Symposium on Principles of Database Systems pp 1– (1987) |

[32] | DOI: 10.1016/0022-0000(82)90011-3 · Zbl 0503.68032 |

[33] | Proceedings of the Twenty-seventh IEEE Symposium on Foundations of Computer Science pp 478– (1986) |

[34] | On the computational complexity of finding a kernel (1973) |

[35] | DOI: 10.1016/S0022-0000(70)80006-X · Zbl 0188.33502 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.