Exact Algorithms for Some Graph Coloring and Covering Problems

Siddharth Bhandari
Vinod M. Prabhakaran
Tuesday, 13 Jun 2017, 11:00 to 12:00
A-201 (STCS Seminar Room)
Inclusion-Exclusion based methods will be presented for solving exactly some graph coloring and covering problems. In particular this solves the problem of finding the Chromatic number of a graph in $O^*(2^n)$ time, which was open till 2006 (Björklund and Husfeldt, FOCS 2006). Then, an alternate approach of using Fast Subset Convolution will be presented: this generalizes the Inclusion-Exclusion based methods at a cost. Finally, an algorithm for computing the b-fold Fractional Chromatic number in $O^*(2^{(n log(2b))})$ time, will be presented.