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
first-order logicsubgraph isomorphism problemdescriptive complexityquantifier depthencoding-independent computation
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)
Related Items (7)
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