论文标题
惠特尼开关的内核
Kernelization of Whitney Switches
论文作者
论文摘要
惠特尼（Whitney）的基本定理从1933年开始断言，2相互连接的G和H是2个同态的，或者等效地，它们的循环矩形是同构的，并且仅当且仅当G通过一系列称为Whitney Switches的操作将G转换为H中时。在本文中，我们考虑了惠特尼定理引起的定量问题：鉴于两个2个呈现图，我们可以通过在大多数k惠特尼开关上使用一个2吗？对于循环，这个问题已经是NP完整的，我们研究了其参数化的复杂性。我们表明，问题允许大小O（k）的内核，因此，当k参数化时，可以固定参数处理。
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.
