Kernelization of Whitney switches

DOI10.1137/20M1367519MaRDI QIDQ4997132zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Petr A. Golovach

Publication date 28 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.13684

zbMATH Keywords

2-isomorphismkernelizationparameterized complexityWhitney switch

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k), and thus, is fixed-parameter tractable when parameterized by k.

Recommendations

• Mutation on knots and Whitney's 2-isomorphism theorem
• Vertex 2-isomorphism
• scientific article; zbMATH DE number 4081581
• A short proof and a strengthening of the Whitney 2-isomorphism theorem on graphs
• On the cycle‐isomorphism of graphs

Cites work

• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• 2-Isomorphic Graphs
• A 2-isomorphism theorem for hypergraphs
• A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry
• An improved kernel size for rotation distance in binary trees
• Computing the flip distance between triangulations
• Dividing a Graph into Triconnected Components
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Flip distance between two triangulations of a point set is NP-complete
• Flips in planar graphs
• Fundamentals of parameterized complexity
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
• Hardness Results for Tournament Isomorphism and Automorphism
• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 863474 (Why is no real title available?)
• scientific article; zbMATH DE number 871927 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Multivariate algorithmics for NP-hard string problems
• Non-Separable and Planar Graphs
• On Whitney's 2‐isomorphism theorem for graphs
• Parameterized algorithms
• Rotation distance is fixed-parameter tractable
• Sorting circular permutations by reversal.
• Sorting strings by reversals and by transpositions
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• Transforming cabbage into turnip
• Vertex insertion approximates the crossing number of apex graphs

Cited in

(1)

• Vertex 2-isomorphism

This page was built for publication: Kernelization of Whitney switches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997132)