2026-07-23T15:20:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12914 2024-03-06T10:51:04Z ddc:004 open_access

Kernelization of Whitney Switches Fomin, Fedor V. Golovach, Petr A. Whitney switch 2-isomorphism Parameterized Complexity kernelization 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 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size 𝒪(k), and thus, is fixed-parameter tractable when parameterized by k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.48 urn:nbn:de:0030-drops-129144 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.48 eng https://creativecommons.org/licenses/by/3.0/legalcode