{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:10Z","timestamp":1787323150822,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["263317"],"award-info":[{"award-number":["263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most $k$ Whitney switches? This problem is already \\sf NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size $\\mathcal{O}(k)$ and thus is fixed-parameter tractable when parameterized by $k$.<\/jats:p>","DOI":"10.1137\/20m1367519","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T13:38:16Z","timestamp":1623937096000},"page":"1298-1336","source":"Crossref","is-referenced-by-count":1,"title":["Kernelization of Whitney Switches"],"prefix":"10.1137","volume":"35","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. Babai,\n                      Graph isomorphism in quasipolynomial time\n                      , in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, ACM, 2016, pp. 684-697.","DOI":"10.1145\/2897518.2897542"},{"key":"atypb2","first-page":"200","author":"Berman P.","year":"2002","journal-title":"New York"},{"key":"atypb3","first-page":"200","author":"Berman P.","year":"1999","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.04.001"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2016.05.002"},{"key":"atypb6","first-page":"114","author":"Bulteau L.","year":"2014","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb7","first-page":"75","author":"Caprara A.","year":"1997","journal-title":"ACM"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.009"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197331995"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.04.023"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00306-5"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi,\n                      Kernelization: Theory of parameterized preprocessing\n                      , Cambridge University Press, Cambridge, 2019.","DOI":"10.1017\/9781107415157"},{"key":"atypb16","first-page":"304","author":"Hannenhalli S.","year":"1996","journal-title":"ACM\/SIAM"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9867-x"},{"key":"atypb20","first-page":"307","author":"Kececioglu J. D.","year":"1994","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188586"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.02.004"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.11.001"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.04.022"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0159-2"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"P. A. Pevzner,\n                      Computational Molecular Biology-An Algorithmic Approach\n                      , MIT Press, Cambridge, MA, 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"atypb27","unstructured":"P. Schweitzer,\n                      A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, LIPIcs 80, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2017, 66."},{"key":"atypb28","first-page":"319","author":"Solomon A.","year":"2003","journal-title":"New York"},{"key":"atypb29","first-page":"301","author":"Thomassen C.","year":"1995","journal-title":"Amsterdam"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190040106"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"W. T. Tutte,\n                      Connectivity in Graphs\n                      , Math. Expositions 15, University of Toronto Press, Toronto, 1966.","DOI":"10.3138\/9781487584863"},{"key":"atypb32","unstructured":"W. T. Tutte,\n                      Graph Theory\n                      , Encyclopedia Math. Appl., Cambridge University Press, Cambridge, 2001."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1789"},{"key":"atypb34","first-page":"572","author":"Wagner F.","year":"2007","journal-title":"New York"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1932-1501641-2"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2307\/2371127"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1367519","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:50Z","timestamp":1787319890000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1367519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1367519"],"URL":"https:\/\/doi.org\/10.1137\/20m1367519","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}