Name
Abstract | ||
|---|---|---|
Let v(F) denote the number of vertices in a fixed connected pattern graph F. We show an infinite family of patterns F such that the existence of a subgraph isomorphic to F is expressible by a first-order sentence of quantifier depth 2/3 v(F) + 1, assuming that the host graph is sufficiently large and connected. However, this is impossible for any F using less than 2/3 v(F) - 2 first-order variables.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3303881 | ACM Transactions on Computational Logic (TOCL) |
Keywords | Field | DocType |
The subgraph isomorphism problem, and variable width, descriptive and computational complexity, first-order logic, quantifier depth | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Isomorphism,Descriptive complexity theory,Sentence,Subgraph isomorphism problem,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1802.02143 | 2 | 1529-3785 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Verbitsky | 1 | 191 | 27.50 |
| Maksim Zhukovskii | 2 | 2 | 4.51 |