{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:50Z","timestamp":1740109310878,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T00:00:00Z","timestamp":1596585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T00:00:00Z","timestamp":1596585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000608","name":"London Mathematical Society","doi-asserted-by":"publisher","award":["SC7-1718-04"],"award-info":[{"award-number":["SC7-1718-04"]}],"id":[{"id":"10.13039\/501100000608","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0022"],"award-info":[{"award-number":["ANR-17-CE40-0022"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K025090\/1"],"award-info":[{"award-number":["EP\/K025090\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2016-258"],"award-info":[{"award-number":["RPG-2016-258"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010653","name":"Masarykova Univerzita","doi-asserted-by":"publisher","award":["MUNI Award in Science and Humanities"],"award-info":[{"award-number":["MUNI Award in Science and Humanities"]}],"id":[{"id":"10.13039\/501100010653","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We resolve the computational complexity of <jats:sc>Graph Isomorphism<\/jats:sc> for classes of graphs characterized by two forbidden induced subgraphs <jats:inline-formula><jats:alternatives><jats:tex-math>$$ H_{1} $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$H_2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>H<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all but six pairs <jats:inline-formula><jats:alternatives><jats:tex-math>$$(H_1,H_2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that <jats:sc>Graph Isomorphism<\/jats:sc> is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between <jats:sc>Graph Isomorphism<\/jats:sc> and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for <jats:inline-formula><jats:alternatives><jats:tex-math>$$(H_1,H_2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>H<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs to five.<\/jats:p>","DOI":"10.1007\/s00453-020-00747-x","type":"journal-article","created":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T12:02:54Z","timestamp":1596628974000},"page":"822-852","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Graph Isomorphism for $$(H_1,H_2)$$-Free Graphs: An\u00a0Almost Complete Dichotomy"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7905-8018","authenticated-orcid":false,"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0170-0503","authenticated-orcid":false,"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9515-6945","authenticated-orcid":false,"given":"Konrad K.","family":"Dabrowski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7295-2663","authenticated-orcid":false,"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5586-5613","authenticated-orcid":false,"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,5]]},"reference":[{"key":"747_CR1","first-page":"684","volume":"2016","author":"L Babai","year":"2016","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. Proc. STOC 2016, 684\u2013697 (2016)","journal-title":"Proc. STOC"},{"key":"747_CR2","first-page":"162","volume":"1983","author":"L Babai","year":"1983","unstructured":"Babai, L., Kantor, W.M., Luks, E.M.: Computational complexity and the classification of finite simple groups. Proc. FOCS 1983, 162\u2013171 (1983)","journal-title":"Proc. FOCS"},{"issue":"1","key":"747_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00453-016-0234-8","volume":"80","author":"R Belmonte","year":"2018","unstructured":"Belmonte, R., Otachi, Y., Schweitzer, P.: Induced minor free graphs: Isomorphism and clique-width. Algorithmica 80(1), 29\u201347 (2018)","journal-title":"Algorithmica"},{"issue":"2","key":"747_CR4","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1137\/18M1235016","volume":"34","author":"A Blanch\u00e9","year":"2020","unstructured":"Blanch\u00e9, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D., Zamaraev, V.: Clique-width for graph classes closed under complementation. SIAM J. Discrete Math. 34(2), 1107\u20131147 (2020)","journal-title":"SIAM J. Discrete Math."},{"key":"747_CR5","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Dabrowski, K.K., Johnson, M., Paulusma, D.: Graph isomorphism for $$(H_1, H_2)$$-free graphs: an almost complete dichotomy. In: Procedings of WADS 2019, LNCS 11646, pp. 181\u2013195 (2019)","DOI":"10.1007\/978-3-030-24766-9_14"},{"key":"747_CR6","unstructured":"Booth, K.S., Colbourn, C.J.: Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Department of Computer Science, University of Waterloo (1979)"},{"key":"747_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.dam.2016.04.003","volume":"211","author":"A Brandst\u00e4dt","year":"2016","unstructured":"Brandst\u00e4dt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of $$H$$-free split graphs. Discrete Appl. Math. 211, 30\u201339 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"747_CR8","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/jgt.22111","volume":"86","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of $$H$$-free chordal graphs. J. Graph Theory 86(1), 42\u201377 (2017)","journal-title":"J. Graph Theory"},{"issue":"1","key":"747_CR9","first-page":"173","volume":"8","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Klembt, T., Mahfud, S.: $$P_6$$- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Math. Theor. Comput. Sci. 8(1), 173\u2013188 (2006)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"747_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13\u201321 (1981)","journal-title":"Networks"},{"key":"747_CR11","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/j.jcss.2017.06.005","volume":"89","author":"KK Dabrowski","year":"2017","unstructured":"Dabrowski, K.K., Dross, F., Paulusma, D.: Colouring diamond-free graphs. J. Comput. Syst. Sci. 89, 410\u2013431 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"747_CR12","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.jcss.2016.06.007","volume":"104","author":"KK Dabrowski","year":"2019","unstructured":"Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding clique-width via perfect graphs. J. Comput. Syst. Sci. 104, 202\u2013215 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"747_CR13","first-page":"1","volume":"456","author":"KK Dabrowski","year":"2019","unstructured":"Dabrowski, K.K., Johnson, M., Paulusma, D.: Clique-width for hereditary graph classes. Lond. Math. Soc. Lect. Note Ser. 456, 1\u201356 (2019)","journal-title":"Lond. Math. Soc. Lect. Note Ser."},{"key":"747_CR14","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.jcss.2019.09.001","volume":"108","author":"KK Dabrowski","year":"2020","unstructured":"Dabrowski, K.K., Lozin, V.V., Paulusma, D.: Clique-width and well-quasi-ordering of triangle-free graph classes. J. Comput. Syst. Sci. 108, 64\u201391 (2020)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"747_CR15","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. Comput. J. 59(5), 650\u2013666 (2016)","journal-title":"Comput. J."},{"key":"747_CR16","unstructured":"de\u00a0Ridder et\u00a0al. H.N.: Information System on Graph Classes and their Inclusions, 2001\u20132020. http:\/\/www.graphclasses.org. Accessed 8 July 2020"},{"key":"747_CR17","first-page":"1","volume":"2019","author":"M Grohe","year":"2019","unstructured":"Grohe, M., Neuen, D.: Canonisation and definability for graphs of bounded rank width. Proc. LICS 2019, 1\u201313 (2019)","journal-title":"Proc. LICS"},{"key":"747_CR18","first-page":"89","volume":"2018","author":"M Grohe","year":"2018","unstructured":"Grohe, M., Neuen, D., Schweitzer, P.: A faster isomorphism test for graphs of small degree. Proc. FOCS 2018, 89\u2013100 (2018)","journal-title":"Proc. FOCS"},{"key":"747_CR19","unstructured":"Grohe, M., Neuen, D., Schweitzer, P., Wiebking, D.: An improved isomorphism test for bounded-tree-width graphs. In: Proceedings of ICALP 2018, LIPIcs, vol. 107, pp. 67:1\u201367:14 (2018)"},{"key":"747_CR20","first-page":"1010","volume":"2015","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. Proc. FOCS 2015, 1010\u20131029 (2015)","journal-title":"Proc. FOCS"},{"issue":"12","key":"747_CR21","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"key":"747_CR22","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.dam.2014.10.026","volume":"216, Part 1","author":"S Kratsch","year":"2017","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Discrete Appl. Math. 216, Part 1, 240\u2013253 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"747_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1137\/140999980","volume":"46","author":"D Lokshtanov","year":"2017","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM J. Comput. 46(1), 161\u2013189 (2017)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"747_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/S0895480102419755","volume":"18","author":"VV Lozin","year":"2004","unstructured":"Lozin, V.V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18(1), 195\u2013206 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"747_CR25","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"747_CR26","unstructured":"Neuen, D.: Graph isomorphism for unit square graphs. In: Proceedings of ESA 2016, LIPIcs, vol. 57, pp. 70:1\u201370:17 (2016)"},{"issue":"1","key":"747_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(88)90143-3","volume":"28","author":"S Olariu","year":"1988","unstructured":"Olariu, S.: Paw-free graphs. Inf. Process. Lett. 28(1), 53\u201354 (1988)","journal-title":"Inf. Process. Lett."},{"key":"747_CR28","doi-asserted-by":"publisher","unstructured":"Ponomarenko, I.N.: Isomorphism problem for classes of graphs closed under contractions. Zapiski Nauchnykh Seminarov (LOMI) 174, 147\u2013177 (1988). (in Russian, English translation in J. Soviet Math. 55(2), 1621\u20131643 (1991). https:\/\/doi.org\/10.1007\/BF01098279)","DOI":"10.1007\/BF01098279"},{"issue":"3","key":"747_CR29","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312\u2013323 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"747_CR30","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1007\/s00224-017-9775-8","volume":"61","author":"P Schweitzer","year":"2017","unstructured":"Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. Theory Comput. Syst. 61(4), 1084\u20131127 (2017)","journal-title":"Theory Comput. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00747-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00747-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00747-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T23:46:53Z","timestamp":1628120813000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00747-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,5]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["747"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00747-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,8,5]]},"assertion":[{"value":"31 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}