The descriptive complexity of subgraph isomorphism without numerics

DOI10.1007/s00224-018-9864-3zbMath1435.68114arXiv1607.08067OpenAlexW2801851744MaRDI QIDQ5919541

M. E. Zhukovskii, Oleg Verbitsky

Publication date: 4 July 2019

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicsubgraph isomorphism problemdescriptive complexityquantifier depthencoding-independent computation

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items (7)

Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ First-order definitions of subgraph isomorphism through the adjacency and order relations ⋮ MSO 0-1 law for recursive random trees ⋮ Unnamed Item ⋮ First-order complexity of subgraph isomorphism via Kneser graphs ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zero-one \(k\)-law
• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• Elements of finite model theory.
• Girth and treewidth
• On the definability of properties of finite graphs
• Strong computational lower bounds via parameterized complexity
• Some recent progress and applications in graph minor theory
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Paw-free graphs
• A restricted second order logic for finite structures
• Succinct definitions in the first order theory of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Is Polynomial Time Choiceless?
• Logical complexity of graphs: a survey
• Powers of tensors and fast matrix multiplication
• Color-coding
• A Short Tutorial on Order-Invariant First-Order Logic
• Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism
• Polynomial bounds for the grid-minor theorem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the $AC^0$ Complexity of Subgraph Isomorphism
• The descriptive complexity of subgraph isomorphism without numerics

This page was built for publication: The descriptive complexity of subgraph isomorphism without numerics