Finding Independent Transversals Efficiently

Abstract

We give an efficient algorithm that, given a graph $G$ and a partition $V_1,\dots ,V_m$ of its vertex set, finds either an independent transversal (an independent set $\{v_1,\dots ,v_m\}$ in $G$ such that $v_i\in V_i$ for each $i$), or a subset $\mathcal{B}$ of vertex classes such that the subgraph of $G$ induced by $\bigcup \mathcal{B}$ has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been applied to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here.

This new version fixes a few typos and adds a brief overview of the analysis to Section 5. There is also further discussion of future work in Section 8