Graphs identified by logics with counting

DOI10.1007/978-3-662-48057-1_25zbMATH Open1465.68101arXiv1503.08792OpenAlexW1809739516MaRDI QIDQ2946347FDOQ2946347

Authors: Sandra Kiefer, P. Schweitzer, Erkal Selman 

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Abstract: We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by C2. Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures. We provide constructions that solve the inversion problem for finite structures in linear time. This problem has previously been shown to be polynomial time solvable by Martin Otto. For graphs, we conclude that every C2-equivalence class contains a graph whose orbits are exactly the classes of the C2-partition of its vertex set and which has a single automorphism witnessing this fact. For general k, we show that such statements are not true by providing examples of graphs of size linear in k which are identified by C3 but for which the orbit partition is strictly finer than the Ck-partition. We also provide identified graphs which have vertex-colored versions that are not identified by Ck.

Full work available at URL: https://arxiv.org/abs/1503.08792

Recommendations

• Graphs Identified by Logics with Counting
• An optimal lower bound on the number of variables for graph identification
• Counting bounded tree depth homomorphisms
• Canonization for two variables and puzzles on the square
• Logics with counting and equivalence

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Relational systems, laws of composition (08A02) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Cites Work

• Practical graph isomorphism. II.
• Random Graph Isomorphism
• An optimal lower bound on the number of variables for graph identification
• On logics with two variables
• Title not available (Why is that?)
• Regular graphs and the spectra of two-variable logic with counting
• Complexity of the two-variable fragment with counting quantifiers
• Canonization for two variables and puzzles on the square
• Sherali-Adams relaxations and indistinguishability in counting logics
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Logical hierarchies in PTIME
• On the Uniqueness of the Triangular Association Scheme
• Title not available (Why is that?)
• Pebble games and linear equations
• Graphs identified by logics with counting
• Finite Variable Logics in Descriptive Complexity Theory
• On the power of color refinement
• Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth

Cited In (12)

• Title not available (Why is that?)
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Title not available (Why is that?)
• Graphs Identified by Logics with Counting
• Graphs identified by logics with counting
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• Graph isomorphism, color refinement, and compactness
• On Tinhofer's linear programming approach to isomorphism testing
• On the power of color refinement
• Choiceless polynomial time with witnessed symmetric choice

This page was built for publication: Graphs identified by logics with counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946347)