Title: Fixed-parameter tractability with respect to tree-widt
|Affiliation:||University of Waterloo|
Abstract: Courcelle’s Theorem says that a very general class of decision problems on graphs is FPT with respect to tree-width. The class of problems is natural and includes colouring, Hamiltonian cycle, and max cut. We will see Courcelle’s algorithm in full generality: for problems definable in the monadic second-order logic of graphs.
200 University Avenue West
Waterloo, ON N2L 3G1