Finding independent transversals efficiently

Source abstract

Abstract We give an efficient algorithm that, given a graph G and a partition V 1 ,…, V m of its vertex set, finds either an independent transversal (an independent set { v 1 ,…, v m } in G such that ${v_i} \in {V_i}$ for each i ), or a subset ${\cal B}$ of vertex classes such that the subgraph of G induced by $\bigcup\nolimits_{\cal B}$ has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been used 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.