WorksMathematics
Efficient Reconfiguration of Independent Transversals
Abstract
We study the reconfiguration of independent transversals in graphs with a prescribed vertex partition. Given a graph with a vertex partition , an independent transversal is an independent set containing exactly one vertex from each part of . The reconfiguration problem concerns transforming one independent transversal into another through a sequence of local changes, while preserving the independent transversal property at every step. For any fixed and , we present a polynomial-time algorithm that, given an -claw-free graph with a vertex partition and two independent transversals and , either finds a polynomial-length reconfiguration path between and , or identifies a nonempty set of partition classes such that the subgraph induced by their union admits a strong dominating set of size at most . Our result provides an algorithmic counterpart to recent connectivity results for the reconfiguration graph of all independent transversals, and establishes polynomial bounds on its diameter under suitable conditions. As a specific application, we obtain a polynomial-time algorithm for reconfiguring perfect matchings in -uniform bipartite hypergraphs , that either produces a polynomial-length reconfiguration path between two given perfect matchings or identifies a subset whose link hypergraph in has a small cover.