School of Technology and Computer Science Seminars

Exact Algorithms for Some Graph Coloring and Covering Problems

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

Tuesday, June 13, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.