Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-11T15:20:36.175Z Has data issue: false hasContentIssue false
  • English
  • Français

Reachability is harder for directed than for undirected finite graphs

Published online by Cambridge University Press:  12 March 2014

Miklos Ajtai  and
Ronald Fagin
Miklos Ajtai
Affiliation:
IBM Almaden Research Center, San Jose, California 95120
Ronald Fagin
Affiliation:
IBM Almaden Research Center, San Jose, California 95120
Get access Rights & Permissions [Opens in a new window]

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 most k, reachability is expressible by an existential monadic second-order sentence.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 1 , March 1990 , pp. 113 - 150
Copyright
Copyright © Association for Symbolic Logic 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[AA]Aggarwal, A. and Anderson, R. J., A random NC algorithm for depth-first search, Proceedings of the Nineteenth ACM Symposium on Theory of Computing (1987), pp. 325–334.Google Scholar
[Aj]Ajtai, M., -formulae on finite structures, Annals of Pure and Applied Logic, vol. 24 (1983), pp. 1–48.CrossRefGoogle Scholar
[AKLLR]Aleliunas, R., Karp, R. M., Lipton, R. J., Lovász, L., and Rackoff, C., Random walks, universal traversal sequences, and the complexity of maze problems, Proceedings of the Twentieth IEEE Symposium on Foundations of Computer Science (1979), pp. 218–223.Google Scholar
[An]Anderson, R., Private communication, 05 1987.Google Scholar
[BK BR]Beeri, C., Kanellakis, P., Bancilhon, F., and Ramakrishnan, R., Bounds on the propagation of selection into logic programs, Proceedings of the Sixth ACM Symposium on Principles of Database Systems (1987), pp. 214–226. (Final version, to appear in Journal of Computer and System Sciences.)CrossRefGoogle Scholar
[BeSi]Berman, P. and Simon, J., Lower bounds on graph threading by probabilistic machines, Proceedings of the Twenty-fourth IEEE Symposium on Foundations of Computer Science (1983), pp. 304–311.Google Scholar
[Bo]Bollobás, B., Random graphs, Academic Press, New York, 1982.Google Scholar
[BoSi]Boppana, R. B. and Sipser, M., The complexity of finite functions, Handbook of Theoretical Computer Science (to appear).Google Scholar
[BCDRT]Borodin, A., Cook, S. A., Dymond, P. W., Ruzzo, W. L., and Tompa, M., Two applications of complementation via inductive counting, Proceedings of the Third Conference on Structure in Complexity Theory (1988), pp. 116–125. (Final version, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, vol. 18 (1989), pp. 559–578.)Google Scholar
[CH]Chandra, A. K. and Harel, D., Structure and complexity of relational-queries, Journal of Computer and System Sciences, vol. 25 (1982), 99–128.CrossRefGoogle Scholar
[Che]Chernoff, H., A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations, Annals of Mathematical Statistics, vol. 23 (1952), pp. 493–507.CrossRefGoogle Scholar
[Chv]Chvátal, V., On the computational complexity of finding a kernel, Report No. CRM-300, Centre de Recherches Mathématiques, Université de Montréal, Montréal, 1973.Google Scholar
[CV]Cole, R. and Vishkin, U., Approximate and exact parallel scheduling with applications to list, tree and graph problems, Proceedings of the Twenty-seventh IEEE Symposium on Foundations of Computer Science (1986), pp. 478–491.Google Scholar
[CR]Cook, S. A. and Rackoff, C. W., Space lower bounds for maze threadability on restricted machines, SIAM Journal on Computing, vol. 9 (1980), pp. 636–652.CrossRefGoogle Scholar
[CW]Coppersmith, D. and Winograd, S., Matrix multiplication via arithmetic progressions, Proceedings of the Nineteenth ACM Symposium on Theory of Computing (1987), pp. 1–6.Google Scholar
[Eh]Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49 (1961), pp. 129–141.CrossRefGoogle Scholar
[Fa1]Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Karp, R., editor), SIAM-AMS Proceedings, vol. 7, 1974, pp. 43–73.Google Scholar
[Fa2]Fagin, R., Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
[Fr]Fraïssé, R., Sur quelques classifications des systèmes de relations, Publications Scientifiques de l'Université d'Alger, vol. 1 (1954), pp. 35–182.Google Scholar
[GJ]Garey, M. and Johnson, D. S., Computers and intractibility: a guide to the theory of NP-completeness, Freeman, San Francisco, California, 1979.Google Scholar
[HMS]Hochschild, P. H., Mayr, E. W., and Siegel, A. R., Parallel Graph Algorithms, Stanford University Technical Report, 1987; to appear in SIAM Journal on Computing.Google Scholar
[Im1]Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
[Im2]Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
[Im3]Immerman, N., Languages which capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
[Im4]Immerman, N., Descriptive and computational complexity, Computational complexity theory, Proceedings of Symposia in Applied Mathematics, vol. 38, American Mathematical Society, Providence, Rhode Island, 1989, pp. 75–91.CrossRefGoogle Scholar
[Ka1]Kanellakis, P., Private communication, 10 1986.Google Scholar
[Ka2]Kanellakis, P., Logic programming and parallel complexity, Foundations of deductive databases and logic programming (Minker, J., editor), Morgan Kaufmann, Los Altos, California, 1988.Google Scholar
[KW]Karchmer, M. and Wigderson, A., Monotone circuits for connectivity require superlogarithmic depth, Proceedings of the Twentieth ACM Symposium on Theory of Computing (1988), pp. 539–550.Google Scholar
[KV]Kolaitis, P. G. and Vardi, M. Y., The decision problem for the probabilities of higher-order properties, Proceedings of the Nineteenth ACM Symposium on Theory of Computing (1987), pp. 425–435.Google Scholar
[Le]Leivant, D., Characterization of complexity classes in higher-order logic, Proceedings of the Second IEEE Conferencee on Structure in Complexity Theory (1987), pp. 203–217. (Revised version, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences, vol. 39 (1989), pp. 51–83.)CrossRefGoogle Scholar
[Lo]Lovász, L., Computing ears and branchings in parallel, Proceedings of the Twenty-sixth IEEE Symposium on Foundations of Computer Science (1985), pp. 464–467.Google Scholar
[Ly]Lynch, J., Complexity classes and theories of finite models, Mathematical Systems Theory, vol. 15 (1982), pp. 127–144.CrossRefGoogle Scholar
[PR]Pan, V. and Reif, J., Efficient parallel solution of linear systems, Proceedings of the Seventeenth ACM Symposium on Theory of Computing (1985), pp. 143–152.Google Scholar
[Ro]de Rougemont, M., Second-order and inductive definability on finite structures, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 33 (1987), pp. 47–63. (Preliminary version appeared as: Uniform definability on structures with successor, Proceedings of the Sixteenth ACM Symposium on Theory of Computing (1984), pp. 409–417.)CrossRefGoogle Scholar
[Sa]Savitch, W. J., Relations between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences, vol. 4 (1970), pp. 177–192.CrossRefGoogle Scholar
[U1]Ullman, J. D., Database theory: past and future, Proceedings of the Sixth ACM Symposium on Principles of Database Systems (1987), pp. 1–10.Google Scholar
[Va]Vardi, M. Y., The complexity of relational query languages, Proceedings of the Fourteenth ACM Symposium on Theory of Computing (1982), pp. 137–146.Google Scholar