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

DOI10.1007/BF01305232zbMath0785.68043OpenAlexW2181072414WikidataQ113847441 ScholiaQ113847441MaRDI QIDQ1204528

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 (only showing first 100 items - show all)

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 ⋮ 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 ⋮ The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3 ⋮ 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 ⋮ Order Reconfiguration under Width Constraints

Uses Software

Unnamed Item

Cites Work

This page was built for publication: An optimal lower bound on the number of variables for graph identification