skip to main content
research-article
Free access

From polynomial time queries to graph structure theory

Published: 01 June 2011 Publication History

Abstract

We give a logical characterization of the polynomial-time properties of graphs with excluded minors: For every class C of graphs such that some graph H is not a minor of any graph in C, a property P of graphs in C is decidable in polynomial time if and only if it is definable in fixed-point logic with counting. Furthermore, we prove that for every class C of graphs with excluded minors there is a k such that a simple combinatorial algorithm, namely "the k-dimensional Weisfeiler--Lehman algorithm," decides isomorphism of graphs in C in polynomial time.

References

[1]
Cai, J., Fürer, M., Immerman, N. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12 (1992), 389--410.
[2]
Chandra, A., Harel, D. Structure and complexity of relational queries. J Comput. Syst. Sci., 25 (1982), 99--128.
[3]
Fagin, R. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM--AMS Proceedings, vol. 7, R. M. Karp, ed. 1974, 43--73.
[4]
Filotti, I. S., Mayer, J. N. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, 236--243.
[5]
Grohe, M. Fixed-point logics on planar graphs. In Proceedings of the 13th IEEE Symposium on Logic in Computer Science, 1998, 6--15.
[6]
Grohe, M., Mariño, J. Definability and descriptive complexity on databases of bounded tree-width. In Proceedings of the 7th International Conference on Database Theory, Lecture Notes in Computer Science, vol. 1540. C. Beeri and P. Buneman, eds. Springer-Verlag, Jerusalem, Israel, 1999, 70--82.
[7]
Gurevich, Y. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science. E. Börger, ed. Computer Science Press, 1988, 1--57.
[8]
Hella, L., Kolaitis, P., Luosto, K. Almost everywhere equivalence of logics in finite model theory. Bull. Symbol. Logic, 2 (1996), 422--443.
[9]
Hopcroft, J., Wong, J. Linear time algorithm for isomorphism of planar graphs. In Proceedings of the 6th ACM Symposium on Theory of Computing, 1974, 172--184.
[10]
Immerman, N. Relational queries computable in polynomial time (extended abstract). In Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, 147--152.
[11]
Immerman, N. Expressibility as a complexity measure: Results and directions. In Proceedings of the 2nd IEEE Symposium on Structure in Complexity Theory, 1987, 194--202.
[12]
Immerman, N., Lander, E. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective. A. Selman, ed. Springer-Verlag, Heidelberg, 1990, 59--81.
[13]
Laubner, B. Capturing polynomial time on interval graphs. In Proceedings of the 25th IEEE Symposium on Logic in Computer Science, 2010, 199--208.
[14]
Luks, E. Isomorphism of graphs of bounded valance can be tested in polynomial time. J. Comput. Syst. Sci., 25 (1982), 42--65.
[15]
Matijasevič, J. Enumerable sets are diophantic. Sov. Math. Dokl., 11 (1970), 345--357.
[16]
Miller, G. L. Isomorphism testing for graphs of bounded genus. In Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, 225--235.
[17]
Otto, M. Bounded Variable Logics and Counting---A Study in Finite Models, Lecture Notes in Logic, vol. 9. Springer-Verlag, Berlin, 1997.
[18]
Ponomarenko, I. N. The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (Teor. Slozhn. Vychisl. 3):147--177, 182, 1988 (in Russian).
[19]
Robertson, N., Seymour, P. Graph minors I--XXIII. Appearing in J. Combin. Theory Ser. B since 1982.
[20]
Robertson, N., Seymour, P. Graph minors XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B, 77 (1999), 1--27.
[21]
Robertson, N., Seymour, P. Graph minors XX. Wagner's conjecture. J. Combin. Theory Ser. B, 92 (2004), 325--357.
[22]
Vardi, M. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, 137--146.

Cited By

View all
  • (2021)On the Power of Symmetric Linear ProgramsJournal of the ACM10.1145/345629768:4(1-35)Online publication date: 29-Jul-2021
  • (2021)Querying in the Age of Graph Databases and Knowledge GraphsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457545(2821-2828)Online publication date: 9-Jun-2021
  • (2016)The Exact Complexity of the First-Order Logic Definability ProblemACM Transactions on Database Systems10.1145/288609541:2(1-14)Online publication date: 11-May-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM
Communications of the ACM  Volume 54, Issue 6
June 2011
134 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/1953122
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2011
Published in CACM Volume 54, Issue 6

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Popular
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)341
  • Downloads (Last 6 weeks)43
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)On the Power of Symmetric Linear ProgramsJournal of the ACM10.1145/345629768:4(1-35)Online publication date: 29-Jul-2021
  • (2021)Querying in the Age of Graph Databases and Knowledge GraphsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457545(2821-2828)Online publication date: 9-Jun-2021
  • (2016)The Exact Complexity of the First-Order Logic Definability ProblemACM Transactions on Database Systems10.1145/288609541:2(1-14)Online publication date: 11-May-2016
  • (2015)Logical Characterizations of Complexity ClassesEncyclopedia of Applied and Computational Mathematics10.1007/978-3-540-70529-1_201(830-834)Online publication date: 21-Nov-2015
  • (2014)P ≠ PWeb Reasoning and Rule Systems10.1007/978-3-319-11113-1_1(1-22)Online publication date: 2014
  • (2012)Fixed-point definability and polynomial time on graphs with excluded minorsJournal of the ACM10.1145/2371656.237166259:5(1-64)Online publication date: 5-Nov-2012

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media