Finding Independent Transversals Efficiently. (arXiv:1811.02687v1 [math.CO])
We give an efficient algorithm that, given a graph $G$ and a partition
$V_1,\ldots,V_m$ of its vertex set, finds either an independent transversal (an
independent set $\{v_1,\ldots,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.查看全文