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

DOI10.1007/BF01305232zbMath0785.68043OpenAlexW2181072414WikidataQ113847441 ScholiaQ113847441MaRDI QIDQ1204528

Neil Immerman, Martin Fuerer, Jin-Yi Cai

Publication date: 10 March 1993

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01305232

zbMATH Keywords

first-order logic with counting graph identification Weisfeiler-Lehman method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical first-order logic (03B10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Order Reconfiguration under Width Constraints, Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas, Weisfeiler-Leman indistinguishability of graphons, Quantum isomorphism of graphs from association schemes, The Weisfeiler-Leman dimension of distance-hereditary graphs, Isomorphism Testing Parameterized by Genus and Beyond, INTERLEAVING LOGIC AND COUNTING, Theory of graph neural networks: representation and learning, Finite Variable Logics in Descriptive Complexity Theory, Isomorphism Testing for Graphs Excluding Small Minors, On symmetric circuits and fixed-point logics, On the Combinatorial Power of the Weisfeiler-Lehman Algorithm, A note on the Kolmogorov data complexity and nonuniform logical definitions, Succinct definitions in the first order theory of graphs, Limitations of Algebraic Approaches to Graph Isomorphism Testing, The QAP-polytope and the graph isomorphism problem, New invariants for the graph isomorphism problem, PEBBLE GAMES AND LINEAR EQUATIONS, Symbioses between mathematical logic and computer science, Semantic Restrictions over Second-Order Logic, On the geometric graph isomorphism problem, Unnamed Item, Canonization for two variables and puzzles on the square, Counting quantifiers, successor relations, and logarithmic space, The first order definability of graphs: Upper bounds for quantifier depth, Choiceless Polynomial Time on Structures with Small Abelian Colour Classes, Equivariant algorithms for constraint satisfaction problems over coset templates, Directions in generalized quantifier theory, Reachability and the power of local ordering, Tight lower and upper bounds for the complexity of canonical colour refinement, Unnamed Item, How to define a linear order on finite models, CFI Construction and Balanced Graphs, Pruning the search tree in the constructive enumeration of molecular graphs, A query language for NC, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, Baby-step giant-step algorithms for the symmetric group, Graph isomorphism, color refinement, and compactness, Graphs Identified by Logics with Counting, Bounds for the Quantifier Depth in Finite-Variable Logics, Is Polynomial Time Choiceless?, An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers, Computational complexity of reconstruction and isomorphism testing for designs and line graphs, Seurat games on Stockmeyer graphs, A query language for NC (extended abstract), Quantum and non-signalling graph isomorphisms, Completeness results for graph isomorphism., On the Descriptive Complexity of Linear Algebra, Unnamed Item, On the Decision Problem for Two-Variable First-Order Logic, The graph isomorphism problem and approximate categories, Generalizations of \(k\)-dimensional Weisfeiler-Leman stabilization, Unnamed Item, Constructing Hard Examples for Graph Isomorphism, The expressive power of fixed-point logic with counting, The hierarchy theorem for generalized quantifiers, Epsilon-logic is more expressive than first-order logic over finite structures, RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!, Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic, Decomposable graphs and definitions with no quantifier alternation, Local WL invariance and hidden shades of regularity, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, A restricted second order logic for finite structures, Descriptive complexity of finite structures: Saving the quantifier rank, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, On the power of combinatorial and spectral invariants, On the Weisfeiler-Leman dimension of fractional packing, Inherent complexity of recursive queries, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Choiceless Computation and Symmetry, Unnamed Item, Benchmark Graphs for Practical Graph Isomorphism, Descriptive complexity of graph spectra, A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On recognizing graphs by numbers of homomorphisms, On the expressive power of linear algebra on graphs, Graph isomorphism restricted by lists, The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, On WL-rank and WL-dimension of some Deza circulant graphs, A restricted second order logic for finite structures, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, Choiceless Logarithmic Space, Fixed-Point Definability and Polynomial Time, The Weisfeiler-Leman algorithm and recognition of graph properties, The Weisfeiler-Leman algorithm and recognition of graph properties, Permutation group approach to association schemes, On a new high dimensional Weisfeiler-Lehman algorithm, Unnamed Item, The first order definability of graphs with separators via the Ehrenfeucht game, Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm, Almost Everywhere Equivalence of Logics in Finite Model Theory, Querying spatial databases via topological invariants, Sherali-Adams relaxations of graph isomorphism polytopes, 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05, Lower bounds for invariant queries in logics with counting., On the separability of cyclotomic schemes over finite fields, Strongly regular graphs with the \(7\)-vertex condition, On fixed-point logic with counting, Isomorphism Test for Digraphs with Weighted Edges., Canonisation and Definability for Graphs of Bounded Rank Width, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs, On polynomial time computation over unordered structures

Uses Software

nauty

Cites Work