{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:06Z","timestamp":1750220946805,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T00:00:00Z","timestamp":1553817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KO 1053\/8-1"],"award-info":[{"award-number":["KO 1053\/8-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009409","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["18-71-00069"],"award-info":[{"award-number":["18-71-00069"]}],"id":[{"id":"10.13039\/100009409","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>v<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) denote the number of vertices in a fixed connected pattern graph\n            <jats:italic>F<\/jats:italic>\n            . We show an infinite family of patterns\n            <jats:italic>F<\/jats:italic>\n            such that the existence of a subgraph isomorphic to\n            <jats:italic>F<\/jats:italic>\n            is expressible by a first-order sentence of quantifier depth 2\/3\n            <jats:italic>v<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) + 1, assuming that the host graph is sufficiently large and connected. However, this is impossible for any\n            <jats:italic>F<\/jats:italic>\n            using less than 2\/3\n            <jats:italic>v<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) - 2 first-order variables.\n          <\/jats:p>","DOI":"10.1145\/3303881","type":"journal-article","created":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T11:57:40Z","timestamp":1554206260000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism"],"prefix":"10.1145","volume":"20","author":[{"given":"Oleg","family":"Verbitsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Humboldt-Universit\u00e4t zu Berlin, Germany"}]},{"given":"Maksim","family":"Zhukovskii","sequence":"additional","affiliation":[{"name":"Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russia"}]}],"member":"320","published-online":{"date-parts":[[2019,3,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_3_1","unstructured":"Reinhard Diestel . 2000. Graph Theory . Springer , New York . Reinhard Diestel. 2000. Graph Theory. Springer, New York."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"volume-title":"Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday (Lecture Notes in Computer Science)","author":"Gr\u00e4del Erich","key":"e_1_2_1_6_1","unstructured":"Erich Gr\u00e4del 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. Erich Gr\u00e4del 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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(1:6)2005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer New York.  Neil Immerman. 1999. Descriptive Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/14099721X"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_2_1_11_1","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer , Berlin . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer, Berlin."},{"key":"e_1_2_1_12_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Ne\u0161et\u0159il Jaroslav","year":"1985","unstructured":"Jaroslav Ne\u0161et\u0159il and Svatopluk Poljak . 1985 . On the complexity of the subgraph problem . Commentat. Math. Univ. Carol. 26 (1985), 415 -- 419 . Jaroslav Ne\u0161et\u0159il and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentat. Math. Univ. Carol. 26 (1985), 415--419.","journal-title":"Commentat. Math. Univ. Carol."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1019"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38536-0_10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90166-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"On the first-order complexity of induced subgraph isomorphism","volume":"15","author":"Verbitsky Oleg","year":"2019","unstructured":"Oleg Verbitsky and Maksim Zhukovskii . 2019 . On the first-order complexity of induced subgraph isomorphism . Log. Meth. Comput. Sci 15 , 1 (2019), 1 -- 24 . Oleg Verbitsky and Maksim Zhukovskii. 2019. On the first-order complexity of induced subgraph isomorphism. Log. Meth. Comput. Sci 15, 1 (2019), 1--24.","journal-title":"Log. Meth. Comput. Sci"},{"volume-title":"The descriptive complexity of subgraph isomorphism without numerics. Theor. Comput. Syst. (2018)","author":"Verbitsky Oleg","key":"e_1_2_1_19_1","unstructured":"Oleg Verbitsky and Maksim Zhukovskii . 2018. The descriptive complexity of subgraph isomorphism without numerics. Theor. Comput. Syst. (2018) . In press . Oleg Verbitsky and Maksim Zhukovskii. 2018. The descriptive complexity of subgraph isomorphism without numerics. Theor. Comput. Syst. (2018). In press."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303881","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3303881","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:40Z","timestamp":1750204420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303881"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,29]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3303881"],"URL":"https:\/\/doi.org\/10.1145\/3303881","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2019,3,29]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}