nach oben

Theory of Computing Systems

Erschienen in:

30.04.2018

The Descriptive Complexity of Subgraph Isomorphism Without Numerics

verfasst von: Oleg Verbitsky, Maksim Zhukovskii

Erschienen in: Theory of Computing Systems | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 the complete graphs K_ℓ and K_ℓ− 1. We show that, for some F, the existence of an F subgraph in sufficiently large connected graphs is definable with quantifier depth ℓ − 3. On the other hand, this is never possible with quantifier depth better than ℓ/2. If we, however, consider definitions over connected graphs with sufficiently large treewidth, the quantifier depth can for some F be arbitrarily small comparing to ℓ but never smaller than the treewidth of F. Moreover, the definitions over highly connected graphs require quantifier depth strictly more than the density of F. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs F on 4 vertices.

Vorheriger Artikel Generic Results for Concatenation Hierarchies

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In his presentation [29], Benjamin Rossman states upper bounds W_FO(F) ≤tw(F) + 1 and D_FO(F) ≤ td(F) for the colorful version of Subgraph Isomorphism studied in [21]. It is not hard to observe that the auxiliary color predicates can be defined in FO[Arb] at the cost of two extra quantified variables by the color-coding method developed in [2]; see also [3, Thm. 4.2].

Note that our language does not contain the truth constants ⊤ and ⊥; otherwise we would have D_v(P₃) = 0.

Very recently [34], we were able to settle this problem by showing that \(D_{v}(F)\le \frac 23\,v(F)+ 1\) for infinitely many pattern graphs F and \(W_{v}(F)>\frac 23\,v(F)-2\) for all F.

Alon, N., Spencer, J.H.: The probabilistic method. Wiley, Hoboken (2016)MATH

Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995). https://doi.org/10.1145/210332.210337 MathSciNetCrossRefMATH

Amano, K.: k-Subgraph isomorphism on AC ⁰ circuits. Comput. Complex. 19(2), 183–210 (2010). https://doi.org/10.1007/s00037-010-0288-y CrossRefMATH

Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996). https://doi.org/10.1137/S0097539793251219 MathSciNetCrossRefMATH

Bollobás, B.: : Random graphs Cambridge Studies in Advanced Mathematics, 2nd edn., vol. 73. Cambridge University Press, Cambridge (2001). https://doi.org/10.1017/CBO9780511814068

Chandran, L.S., Subramanian, C.R.: Girth and treewidth. J. Comb. Theory, Ser. B 93(1), 23–32 (2005). https://doi.org/10.1016/j.jctb.2004.05.004 MathSciNetCrossRefMATH

Chekuri, C., Chuzhoy, J.: Polynomial Bounds for the Grid-Minor Theorem. In: Proceedings of the 46Th ACM Symposium on Theory of Computing (STOC’14), pp. 60–69 (2014). https://doi.org/10.1145/2591796.2591813

Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346–1367 (2006). https://doi.org/10.1016/j.jcss.2006.04.007 MathSciNetCrossRefMATH

Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990). https://doi.org/10.1016/0890-5401(90)90043-H MathSciNetCrossRefMATH

10.

Dawar, A.: A restricted second order logic for finite structures. Inf. Comput. 143(2), 154–174 (1998). https://doi.org/10.1006/inco.1998.2703 MathSciNetCrossRefMATH

11.

Diestel, R.: Graph theory. Springer, New York (2000)MATH

12.

Ebbinghaus, H.D., Flum, J.: Finite Model Theory, Enlarged Edn. Springer Monographs in Mathematics. Springer-Verlag, Berlin (2006)

13.

Floderus, P., Kowaluk, M., Lingas, A., Lundell, E.: Induced Subgraph Isomorphism: Are some patterns substantially easier than others? Theor. Comput. Sci. 605, 119–128 (2015). https://doi.org/10.1016/j.tcs.2015.09.001 MathSciNetCrossRefMATH

14.

Gall, F.L.: Powers of tensors and fast matrix multiplication. In: Proc. of the Int. Symposium on Symbolic and Algebraic Computation (ISSAC’14), pp 296–303. ACM (2014). https://doi.org/10.1145/2608628.2608664

15.

Grädel, E., Grohe, M.: 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. https://doi.org/10.1007/978-3-319-23534-9_11, vol. 9300, pp 193–209. Springer (2015)

16.

Immerman, N.: Descriptive complexity. Springer, New York (1999). https://doi.org/10.1007/978-1-4612-0539-5 CrossRefMATH

17.

Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000)CrossRefMATH

18.

Kawarabayashi, K., Mohar, B.: Some recent progress and applications in graph minor theory. Graphs Comb. 23(1), 1–46 (2007). https://doi.org/10.1007/s00373-006-0684-x MathSciNetCrossRefMATH

19.

Kawarabayashi, K., Rossman, B.: An excluded-minor approximation of tree-depth. Manuscript (2016)

20.

Koucký, M., Lautemann, C., Poloczek, S., Thėrien, D.: Circuit Lower Bounds via Ehrenfeucht-Fraïssé Games. In: Proceedings of the 21St Ann. IEEE Conference on Computational Complexity (CCC’06), pp. 190–201 (2006). https://doi.org/10.1109/CCC.2006.12

21.

Li, Y., Razborov, A.A., Rossman, B.: On the AC⁰ complexity of Subgraph Isomorphism. SIAM J. Comput. 46 (3), 936–971 (2017). https://doi.org/10.1137/14099721X MathSciNetCrossRefMATH

22.

Libkin, L.: Elements of finite model theory. Texts in theoretical computer science. An EATCS series. Springer, Berlin (2004). https://doi.org/10.1007/978-3-662-07003-1 CrossRef

23.

Nešetřil, J., Poljak, S.: On the complexity of the subgraph problem. Commentat. Math. Univ. Carol. 26, 415–419 (1985)MathSciNetMATH

24.

Olariu, S.: Paw-free graphs. Inf. Process. Lett. 28, 53–54 (1988). https://doi.org/10.1016/0020-0190(88)90143-3 MathSciNetCrossRefMATH

25.

Pikhurko, O., Verbitsky, O.: Logical Complexity of Graphs: a Survey. In: Grohe, M., Makowsky, J. (eds.) Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, vol. 558, pp 129–179. American Mathematical Society (AMS), Providence (2011)

26.

Pinsker, M.S.: On the complexity of a concentrator. In: Annual 7th International Teletraffic Conference, pp. 318/1–318/4 (1973)

27.

Rossman, B.: On the Constant-Depth Complexity of K-Clique. In: Proceedings of the 40th Ann. ACM Symposium on Theory of Computing (STOC’08), pp. 721–730. ACM (2008). https://doi.org/10.1145/1374376.1374480 https://doi.org/10.1145/1374376.1374480

28.

Rossman, B.: An improved homomorphism preservation theorem from lower bounds in circuit complexity. SIGLOG News 3(4), 33–46 (2016). http://dl.acm.org/citation.cfm?id=3026746

29.

Rossman, B.: Lower bounds for Subgraph Isomorphism and consequences in first-order logic. Talk in the Workshop on Symmetry, Logic. Computation at the Simons Institute, Berkeley (2016). https://simons.berkeley.edu/talks/benjamin-rossman-11-08-2016

30.

Schweikardt, N.: A short tutorial on order-invariant first-order logic. In: Proceedings of the 8th Int. Computer Science Symposium in Russia (CSR’13), Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-642-38536-0_10, vol. 7913, pp 112–126. Springer (2013)

31.

Turȧn, G.: On the definability of properties of finite graphs. Discret. Math. 49(3), 291–302 (1984). 10.1016/0012-365X(84)90166-3MathSciNetCrossRef

32.

Verbitsky, O., Zhukovskii, M.: The descriptive complexity of Subgraph Isomorphism without numerics. In: Weil, P. (ed.) Proceedings of the 12th Int. Computer Science Symposium in Russia (CSR’17), Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-319-58747-9_27, vol. 10304, pp 308–322. Springer (2017)

33.

Verbitsky, O., Zhukovskii, M.: On the first-order complexity of Induced Subgraph Isomorphism. In: Proceedings of the 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), LIPIcs—Leibniz International Proceedings in Informatics, vol. 82, pp. 40:1–40:16 (2017)

34.

Verbitsky, O., Zhukovskii, M.: Tight bounds on the asymptotic descriptive complexity of Subgraph Isomorphism. E-print: arXiv:https://arxiv.org/abs/1802.02143(2018)

35.

Wormald, N.: Models of Random Regular Graphs. In: Surveys in Combinatorics, pp. 239–298. Cambridge University Press (1999)

36.

Zhukovskii, M.: Zero-one k-law. Discret. Math. 312, 1670–1688 (2012)MathSciNetCrossRefMATH

Titel: The Descriptive Complexity of Subgraph Isomorphism Without Numerics
verfasst von: Oleg Verbitsky
Maksim Zhukovskii
Publikationsdatum: 30.04.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9864-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2019

Generic Results for Concatenation Hierarchies

Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)

Verification of Quantum Computation: An Overview of Existing Approaches

On Algorithmic Statistics for Space-bounded Algorithms

Green’s Relations in Deterministic Finite Automata

The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0

Premium Partner