Cliques, Coloring and Satisfiability: from structure to algorithms
- Speaker: Dr Vadim Lozin, Mathematics Institute, University of Warwick.
- Date: Wednesday, 20 November 2013 from 16:30 to 17:30
- Location: Room 160, Birkbeck Main Building
Cliques, coloring and satisfiability are three central problems of theoretical computer science each of which is generally NP-hard. On the other hand, each of them may become tractable when restricted to instances of particular structure. In this talk we analyze how the structure of the input can affect the computational complexity of these problems. We also discuss some algorithmic tools to solve the problems with a focus given to transformations of graphs and of CNF formulas.