Exact Algorithms for Some Graph Coloring and Covering Problems

by Siddharth Bhandari (School of Technology and Computer Science, TIFR)

Tuesday 13 Jun 2017, 11:00 → 12:00 Asia/Kolkata

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.