{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T02:18:37Z","timestamp":1772849917436,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T00:00:00Z","timestamp":1634860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation DFG Koselleck","award":["GR 1492\/14-1"],"award-info":[{"award-number":["GR 1492\/14-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            We classify graphs and, more generally, finite relational structures that are identified by\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^2<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^2<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures.\n          <\/jats:p>\n          <jats:p>\n            We provide constructions that solve the inversion problem for finite relational structures in linear time. By a result due to Otto, this problem has been known to be polynomial-time solvable. For graphs, we conclude that every\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^2<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -equivalence class contains a representative whose orbits are exactly the classes of the\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^2<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -partition of its vertex set and which has a single automorphism witnessing this fact.\n          <\/jats:p>\n          <jats:p>\n            We show that such statements are not true for general\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">k<\/jats:tex-math>\n            <\/jats:inline-formula>\n            by providing examples of graphs of order linear in\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">k<\/jats:tex-math>\n            <\/jats:inline-formula>\n            which are identified by\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^3<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , but for which the orbit partition is strictly finer than the\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^k<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -partition. We also construct identified graphs which have vertex-colored versions that are not identified by\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJax\">C^k<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>","DOI":"10.1145\/3417515","type":"journal-article","created":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T01:08:26Z","timestamp":1634951306000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Graphs Identified by Logics with Counting"],"prefix":"10.1145","volume":"23","author":[{"given":"Sandra","family":"Kiefer","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Lehrstuhl Informatik 7, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"TU Kaiserslautern, Algorithms and Complexity Group, Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erkal","family":"Selman","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Lehrstuhl Informatik 7, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Graph isomorphism, color refinement, and compactness","volume":"1502","author":"Arvind Vikraman","year":"2015","unstructured":"Vikraman Arvind, Johannes K\u00f6bler, Gaurav Rattan, and Oleg Verbitsky. 2015. Graph isomorphism, color refinement, and compactness. CoRR abs\/1502.01255.","journal-title":"CoRR"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22177-9_26"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0147-6"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/120867834"},{"key":"e_1_3_2_6_2","unstructured":"L\u00e1szl\u00f3 Babai. 1979. Lectures on Graph Isomorphism. Mimeographed lecture notes."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.8"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_13"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90016-0"},{"key":"e_1_3_2_12_2","first-page":"604","article-title":"The Uniqueness and nonuniqueness of the triangular association scheme","volume":"3","author":"Chang Li-Chien","year":"1959","unstructured":"Li-Chien Chang. 1959. The Uniqueness and nonuniqueness of the triangular association scheme. Sci. Record. 3 (1959), 604\u2013613.","journal-title":"Sci. Record."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_25"},{"key":"e_1_3_2_14_2","first-page":"40:1\u201340:14","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","author":"Dell Holger","year":"2018","unstructured":"Holger Dell, Martin Grohe, and Gaurav Rattan. 2018. Lov\u00e1sz meets Weisfeiler and Leman. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. 40:1\u201340:14. DOI: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.40"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00308-9"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614957"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.2307\/420954"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2015.28"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177705914"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3436980.3436982"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_25"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/130943625"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.69"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.11"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.088.020"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90017-4"},{"key":"e_1_3_2_29_2","volume-title":"R\u00e9cr\u00e9ations Math\u00e9matiques","author":"Lucas Edouard","year":"1960","unstructured":"Edouard Lucas. 1960. R\u00e9cr\u00e9ations Math\u00e9matiques. Librairie Scientifique et Technique Albert Blanchard, Paris. xxv+254 pages."},{"key":"e_1_3_2_30_2","first-page":"45","article-title":"Practical graph isomorphism","volume":"30","author":"McKay Brendan D.","year":"1981","unstructured":"Brendan D. McKay. 1981. Practical graph isomorphism. Congressus Numerantium 30 (1981), 45\u201387.","journal-title":"Congressus Numerantium"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00047-4"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5791-1"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_3_2_37_2","volume-title":"Introduction to Graph Theory","author":"West Douglas B.","year":"2000","unstructured":"Douglas B. West. 2000. Introduction to Graph Theory (2nd ed.). Pearson."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,22]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3417515"],"URL":"https:\/\/doi.org\/10.1145\/3417515","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,22]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}