{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:08:45Z","timestamp":1766178525982,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["CLASSIS","MULTIVAL"],"award-info":[{"award-number":["CLASSIS","MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>subgraph complement<\/jats:italic> of the graph <jats:italic>G<\/jats:italic> is a graph obtained from <jats:italic>G<\/jats:italic> by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph <jats:italic>G<\/jats:italic> and graph class <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathscr {G}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, is there a subgraph complement of <jats:italic>G<\/jats:italic> which is in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathscr {G}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>? We show that this problem can be solved in polynomial time for various choices of the graphs class <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathscr {G}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such as bipartite, <jats:italic>d<\/jats:italic>-degenerate, or cographs. We complement these results by proving that the problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathrm{NP}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>NP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete when <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathscr {G}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>G<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the class of regular graphs.<\/jats:p>","DOI":"10.1007\/s00453-020-00677-8","type":"journal-article","created":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T05:02:56Z","timestamp":1580533376000},"page":"1859-1880","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Subgraph Complementation"],"prefix":"10.1007","volume":"82","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3896-3166","authenticated-orcid":false,"given":"Torstein J. F.","family":"Str\u00f8mme","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,1]]},"reference":[{"key":"677_CR1","unstructured":"Blanch\u00e9, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D., Zamaraev, V.: Clique-width for graph classes closed under complementation. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, 21\u201325 Aug 2017, Aalborg, Denmark, Volume 83 of LIPIcs, pp. 73:1\u201373:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"1\u20133","key":"677_CR2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0012-365X(93)90357-Y","volume":"114","author":"A Bouchet","year":"1993","unstructured":"Bouchet, A.: Recognizing locally equivalent graphs. Discrete Math. 114(1\u20133), 75\u201386 (1993)","journal-title":"Discrete Math."},{"key":"677_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Volume 138 of Encyclopedia of Mathematics and Its Applications","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Volume 138 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2012)"},{"issue":"2","key":"677_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"677_CR5","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"677_CR6","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B Courcelle","year":"2007","unstructured":"Courcelle, B., Oum, S.: Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory Ser. B 97(1), 91\u2013126 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"key":"677_CR7","doi-asserted-by":"crossref","unstructured":"Ehrenfeucht, A., Hage, J., Harju, T., Rozenberg, G.: Complexity issues in switching of graphs. In: Theory and Application of Graph Transformations, 6th International Workshop, TAGT\u201998, Paderborn, Germany, 16\u201320 Nov 1998, Selected Papers, Volume 1764 of Lecture Notes in Computer Science, pp. 59\u201370. Springer, Berlin (2000)","DOI":"10.1007\/978-3-540-46464-8_5"},{"issue":"3","key":"677_CR8","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1137\/S0895480100384055","volume":"16","author":"T Feder","year":"2003","unstructured":"Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM J. Discrete Math. 16(3), 449\u2013478 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"677_CR9","unstructured":"Fomin, F.V., Golovach, P.A., Str\u00f8mme, T.J.F., Thilikos, D.M.: Partial complementation of graphs. In: David, E. (eds.) 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 21:1\u201321:13, Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"677_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"677_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"677_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1(3), 275\u2013284 (1981)","journal-title":"Combinatorica"},{"issue":"3","key":"677_CR13","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"key":"677_CR14","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J.: On the hardness of switching to a small number of edges. Computing and Combinatorics: 22nd International Conference. COCOON 2016, Ho Chi Minh City, Vietnam, 2\u20134 Aug 2016, Proceedings, Volume 9797 of Lecture Notes in Computer Science, pp. 159\u2013170. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-42634-1_13"},{"issue":"4","key":"677_CR15","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1002\/jgt.21745","volume":"75","author":"E Jel\u00ednkov\u00e1","year":"2014","unstructured":"Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J.: On switching to H-free graphs. J. Graph Theory 75(4), 387\u2013405 (2014)","journal-title":"J. Graph Theory"},{"issue":"2","key":"677_CR16","first-page":"19","volume":"13","author":"E Jel\u00ednkov\u00e1","year":"2011","unstructured":"Jel\u00ednkov\u00e1, E., Such\u00fd, O., Hlinen\u00fd, P., Kratochv\u00edl, J.: Parameterized problems related to Seidel\u2019s switching. Discrete Math. Theor. Comput. Sci. 13(2), 19\u201344 (2011)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"12","key":"677_CR17","doi-asserted-by":"crossref","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kaminski","year":"2009","unstructured":"Kaminski, M., Lozin, V.V., Milanic, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"key":"677_CR18","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J.: Complexity of hypergraph coloring and Seidel\u2019s switching. In: Graph-Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003, Elspeet, The Netherlands, 19\u201321 June 2003, Revised Papers, Volume 2880 of Lecture Notes in Computer Science, pp. 297\u2013308. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-39890-5_26"},{"key":"677_CR19","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J., Ne\u0161et\u0159il, J., Z\u00fdka, O.: On the computational complexity of Seidel\u2019s switching. In: Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Volume 51 of Annals Discrete Mathematics, pp. 161\u2013166. North-Holland, Amsterdam (1992)","DOI":"10.1016\/S0167-5060(08)70622-8"},{"issue":"1","key":"677_CR20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"677_CR21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.dam.2016.08.006","volume":"231","author":"S Oum","year":"2017","unstructured":"Oum, S.: Rank-width: algorithmic and structural results. Discrete Appl. Math. 231, 15\u201324 (2017)","journal-title":"Discrete Appl. Math."},{"key":"677_CR22","unstructured":"Seidel, J.J.: Graphs and two-graphs, pp. 125\u2013143. Congressus Numerantium, No. X (1974)"},{"key":"677_CR23","unstructured":"Seidel, J.J.: A survey of two-graphs, pp. 481\u2013511. Atti dei Convegni Lincei, No. 17 (1976)"},{"key":"677_CR24","unstructured":"Seidel, J.J., Taylor, D.E.: Two-graphs, a second survey. In: Algebraic Methods in Graph Theory, Volume I, II (Szeged, 1978)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00677-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00677-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00677-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,31]],"date-time":"2021-01-31T00:11:55Z","timestamp":1612051915000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00677-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,1]]},"references-count":24,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["677"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00677-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,1]]},"assertion":[{"value":"30 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}