Advertisement
Published in:
2015 | OriginalPaper | Chapter
Graphs Identified by Logics with Counting
Authors : Sandra Kiefer, Pascal Schweitzer, Erkal Selman
Published in: Mathematical Foundations of Computer Science 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We classify graphs and, more generally, finite relational structures that are identified by \({C^{2}}\), 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 \({C^{2}}\). 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 \({C^{2}}\)-equivalence class contains a graph whose orbits are exactly the classes of the \({C^{2}}\)-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 \({C^{3}}\) but for which the orbit partition is strictly finer than the \(C^k\)-partition. We also provide identified graphs which have vertex-colored versions that are not identified by \(C^k\).