An optimal lower bound on the number of variables for graph identification

Combinatorica - Tập 12 - Trang 389-410 - 1992
Jin-Yi Cai1, Martin Fürer2, Neil Immerman3
1Computer Science Dept., Princeton University, Princeton
2Computer Science Dept., University of Massachusetts, Amherst
3Computer Science Dept., Pennsylvania State University, University Park

Tóm tắt

In this paper we show that Ω(n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k−1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.

Tài liệu tham khảo

A. V. Aho, J. E. Hopcroft andJ. D. Ullman:The Design and Analysis of Computer Algorithms, Addison-Wesley (1974). M. Ajtai: Recursive Construction for 3-Regular Expanders,28th IEEE Symp. on Foundations of Computer Science (1987), 295–304. L. Babai: Monte Carlo Algorithms in Graph Isomorphism Testing, Tech. Rep. DMS 79-10, Université de Montréal, 1979. L. Babai: On the Complexity of Canonical Labeling of Strongly Regular Graphs,SIAM J. Computing 9 (1980), 212–216. L. Babai: Moderately Exponential Bound for Graph Isomorphism,Proc. Conf. on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Springer, 1981, 34–50. L. Babai: On the Order of Uniprimitive Permutation Groups,Annals of Math. 113 (1981), 553–568. L. Babai:Permutation Groups, Coherent Configurations, and Graph Isomorphism, D. Sc. Thesis, Hungarian Acad. Sci., 1984 (in Hungarian). L. Babai, P. Erdős, andS. M. Selkow: Random Graph Isomorphism,SIAM J. on Comput. 9 (1980), 628–635. L. Babai, W. M. Kantor, andE. M. Luks: Computational Complexity and the Classification of Finite Simple Groups,24th IEEE Symp. on Foundations of Computer Science (1983), 162–171. L. Babai andL. Kučera: Canonical Labelling of Graphs in Linear Average Time,20th IEEE Symp. on Foundations of Computer Science (1979), 39–46. L. Babai andE. M. Luks: Canonical Labeling of Graphs,15th ACM Symposium on Theory of Computing (1983), 171–183. D. M. Barrington, N. Immerman, andH. Straubing: On Uniformity Within NC1,J. Comput. System Sci. 41, No. 3 (1990), 274–306. L. Babai andR. Mathon: Talk at the South-East Conference on Combinatorics and Graph Theory, 1980. P. J. Cameron: 6-Transitive Graphs,J. Combinat. Theory B 28, (1980), 168–179. A. Chandra andD. Harel: Structure and Complexity of Relational Queries,J. Comput. System Sci. 25 (1982), 99–128. A. Ehrenfeucht: An Application of Games to the Completeness Problem for Formalized Theories,Fund. Math. 49 (1961), 129–141. R. Fraïssé: Sur quelques classifications des systèms de relations,Publ. Sci. Univ. Alger 1 (1954), 35–182. M. Fürer, W. Schnyder, andE. Specker: Normal Forms for Trivalent Graphs and Graphs of Bounded Valence,15th ACM Symposium on Theory of Computing (1983), 161–170. Ya. Yu. Gol'fand andM. H. Klin: Onk-Regular Graphs, in:Algorithmic Research in Combinatorics, Nauka Publ., Moscow, 1978, 76–85. Yu. Gurevich: Logic and the Challenge of Computer Science, in:Current Trends in Theoretical Computer Science, ed. Egon Börger, Computer Science Press, 1988, 1–57. D. G. Higman: Coherent Configurations I.: Ordinary Representation Theory,Geometriae Dedicata 4 (1975), 1–32. N. Immerman: Number of Quantifiers is Better than Number of Tape Cells,J. Comput. System Sci. 22, No. 3 (1981), 384–406. N. Immerman: Upper and Lower Bounds for First Order Expressibility,J. Comput. System Sci. 25, No. 1 (1982), 76–98. N. Immerman: Relational Queries Computable in Polynomial Time,Information and Control 68 (1986), 86–104. N. Immerman: Languages That Capture Complexity Classes,SIAM J. Computing 16, No. 4 (1987), 760–778. N. Immerman andD. Kozen: Definability with Bounded Number of Bound Variables,Information and Computation 83 (1989), 121–139. N. Immerman andE. S. Lander: Describing Graphs: A First-Order Approach to Graph Canonization, in:Complexity Theory Retrospective, Alan Selman, ed., Springer-Verlag, 1990, 59–81. N. Immerman, S. Patnaik, andD. Stemple: The Expressiveness of a Family of Finite Set Languages,Tenth ACM Symposium on Principles of Database Systems (1991), 37–52. L. Kučera: Canonical Labeling of Regular Graphs in Linear Average Time,28th IEEE Symp. on Foundations of Computer Science (1987), 271–279. M. H. Klin, M. E. Muzichuk, andI. A. Faradžev: Cellular Rings and Groups of Automorphism of Graphs, Introductory Article to a Book to be Published by D. Reidel Publ. Co. M. Ch. Klin, R. Pöschel, andK. Rosenbaum: Angewandte Algebra, Vieweg & Sohn Publ., Braunschweig 1988. R. Lipton: The Beacon Set Approach to Graph Isomorphism, Yale Dept. Comp. Sci. preprint No. 135, 1978. E. M. Luks: Isomorphism of Graphs of Bounded Valence Can be Tested in Polynomial Time,J. Comput. System Sci. 25 (1982), 42–65. R. Mathon: A Note On the Graph Isomorphism Counting Problem,Inform. Proc. Let. 8 (1979), 131–132. B. D. McKay: Nauty User's Guide (Version 1.2), Tech. Rep. TR-CS-87-03, Dept. Computer Science, Austral. National Univ., Melbourne, 1987. G. L. Miller: On then logn Isomorphism Technique,10th ACM Symposium on Theory of Computing (1978), 51–58. R. C. Read andD. G. Corneil: The Graph Isomorphism Disease,J. Graph Theory 1 (1977), 339–363. M. Vardi: Complexity of Relational Query Languages,14th ACM Symposium on Theory of Computing (1982), 137–146. B. Weisfeiler, ed.:On Construction and Identification of Graphs, Lecture Notes in Mathematics 558, Springer, 1976. B. Weisfeiler andA. A. Lehman: A Reduction of a Graph to a Canonical Form and an Algebra Arising during this Reduction, (in Russian),Nauchno-Technicheskaya Informatsia, Seriya 2,9 (1968), 12–16. V. N. Zemlyachenko, N. Kornienko, andR. I. Tyshkevich:Graph Isomorphism Problem, (in Russian), The Theory fo Computation I, Notes Sci. Sem. LOMI 118, 1982.