betaFeedback

WorksMathematics

Efficient Reconfiguration of Independent Transversals

Abstract

We study the reconfiguration of independent transversals in graphs with a prescribed vertex partition. Given a graph GG with a vertex partition V=(V1,…,Vm)\mathcal{V}=(V_1,\ldots,V_m), an independent transversal is an independent set containing exactly one vertex from each part ViV_i of V\mathcal{V}. 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 r∈Nr\in\mathbb{N} and ε>0ε>0, we present a polynomial-time algorithm that, given an rr-claw-free graph GG with a vertex partition V=(V1,…,Vm)\mathcal{V}=(V_1,\ldots,V_m) and two independent transversals SS and RR, either finds a polynomial-length reconfiguration path between SS and RR, or identifies a nonempty set of partition classes B⊆V\mathcal{B}\subseteq\mathcal{V} such that the subgraph induced by their union admits a strong dominating set of size at most (2+ε)∣B∣(2+ε)|\mathcal{B}|. 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 rr-uniform bipartite hypergraphs H=(A,B,E)H=(A,B,E), that either produces a polynomial-length reconfiguration path between two given perfect matchings or identifies a subset S⊆AS\subseteq A whose link hypergraph ESE_S in BB has a small cover.

Paper details

vlnc:W_mg8q8qkr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6

View statement
Looking for related papers…