Title: Finding Independent Transversals Efficiently
| Speaker: | Alessandra Graf |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: Let G be a graph whose vertex set is partitioned into classes V1,..., Vm. An independent transversal of G with respect to (V1,...,Vm) is an independent set {v1,...,vm} in G such that vi is in Vi for each i.
In this talk, we present an efficient algorithm that, given a graph G and vertex partition (V1,...,Vm), finds either an independent transversal of G with respect to (V1,...,Vm) or a subset B of vertex classes such that the subgraph induced by the vertices in the classes of 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. We will discuss algorithmic versions of some of these applications as time allows.