Combinatorial Optimization Reading Group- Rose McCarty

Title: Fixed-parameter tractability with respect to tree-widt

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.