Graphs identified by logics with counting

DOI10.1007/978-3-662-48057-1_25MaRDI QIDQ2946347zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(12)

• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• scientific article; zbMATH DE number 6739879 (Why is no real title available?)
• 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)