More Web Proxy on the site http://driver.im/

research-article

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism

Authors:

Oleg Verbitsky,

Maksim ZhukovskiiAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 20, Issue 2

Article No.: 9, Pages 1 - 18

https://doi.org/10.1145/3303881

Published: 29 March 2019 Publication History

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.

References

[1]

Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844--856.

Digital Library

[2]

László Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th ACM SIGACT Symposium on Theory of Computing (STOC’16). ACM, New York, 684--697.

Digital Library

[3]

Reinhard Diestel. 2000. Graph Theory. Springer, New York.

[4]

Peter Floderus, Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. 2015. Induced subgraph isomorphism: Are some patterns substantially easier than others? Theor. Comput. Sci. 605 (2015), 119--128.

Digital Library

[5]

François Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’14). ACM, New York, 296--303.

Digital Library

[6]

Erich Grädel and Martin Grohe. 2015. Is polynomial time choiceless? In Fields of Logic and Computation II, Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday (Lecture Notes in Computer Science), Vol. 9300. Springer, Cham, 193--209.

[7]

Martin Grohe and Nicole Schweikardt. 2005. The succinctness of first-order logic on linear orders. Log. Meth. Comput. Sci. 1, 1 (2005), 1--25.

[8]

Neil Immerman. 1982. Upper and lower bounds for first-order expressibility. J. Comput. Syst. Sci. 25, 1 (1982), 76--98.

[9]

Neil Immerman. 1999. Descriptive Complexity. Springer, New York.

[10]

Yuan Li, Alexander A. Razborov, and Benjamin Rossman. 2017. On the AC<sup>0</sup> complexity of subgraph isomorphism. SIAM J. Comput. 46, 3 (2017), 936--971.

[11]

Leonid Libkin. 2004. Elements of Finite Model Theory. Springer, Berlin.

Digital Library

[12]

Jaroslav Nešetřil and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentat. Math. Univ. Carol. 26 (1985), 415--419.

[13]

Bogdan Oporowski, James G. Oxley, and Robin Thomas. 1993. Typical subgraphs of 3- and 4-connected graphs. J. Comb. Theor., Ser. B 57, 2 (1993), 239--257.

Digital Library

[14]

Oleg Pikhurko, Helmut Veith, and Oleg Verbitsky. 2006. The first-order definability of graphs: Upper bounds for quantifier depth. Disc. Appl. Math. 154, 17 (2006), 2511--2529.

Digital Library

[15]

Nicole Schweikardt. 2013. A short tutorial on order-invariant first-order logic. In Proceedings of the 8th International Computer Science Symposium in Russia (CSR’13) (Lecture Notes in Computer Science), Vol. 7913. Springer, Berlin, 112--126.

[16]

György Turán. 1984. On the definability of properties of finite graphs. Disc. Math. 49, 3 (1984), 291--302.

Digital Library

[17]

Moshe Y. Vardi. 1995. On the complexity of bounded-variable queries. In Proceedings of the 14th ACM Symposium on Principles of Database Systems. ACM Press, New York, 266--276.

Digital Library

[18]

Oleg Verbitsky and Maksim Zhukovskii. 2019. On the first-order complexity of induced subgraph isomorphism. Log. Meth. Comput. Sci 15, 1 (2019), 1--24.

[19]

Oleg Verbitsky and Maksim Zhukovskii. 2018. The descriptive complexity of subgraph isomorphism without numerics. Theor. Comput. Syst. (2018). In press.

Cited By

Grigoryan OMakarov MZhukovskii M(2020)First-order definitions of subgraph isomorphism through the adjacency and order relationsMoscow Journal of Combinatorics and Number Theory10.2140/moscow.2020.9.2939:3(293-302)Online publication date: 15-Oct-2020
https://doi.org/10.2140/moscow.2020.9.293

Index Terms

Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity theory and logic
  2. Logic
    1. Finite Model Theory

Recommendations

The Descriptive Complexity of Subgraph Isomorphism Without Numerics

Let F be a connected graph with ℓ vertices. The existence of a subgraph isomorphic to F can be defined in first-order logic with quantifier depth no better than ℓ, simply because no first-order formula of smaller quantifier depth can distinguish between ...
Induced subgraph isomorphism

The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced ...
The subgraph isomorphism problem for outerplanar graphs

This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 20, Issue 2

April 2019

220 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/3313982

Editor:
Orna Kupferman
School of Computer Science and Engineering, Hebrew University, Israel

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2019

Accepted: 01 January 2019

Received: 01 July 2018

Published in TOCL Volume 20, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
86
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Grigoryan OMakarov MZhukovskii M(2020)First-order definitions of subgraph isomorphism through the adjacency and order relationsMoscow Journal of Combinatorics and Number Theory10.2140/moscow.2020.9.2939:3(293-302)Online publication date: 15-Oct-2020
https://doi.org/10.2140/moscow.2020.9.293

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents