An optimal lower bound on the number of variables for graph identification
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.