Combinatorics Seminar

When: Sunday, April 19, 10am
Where: Schreiber 309
Speaker: Zvi Gregory Gutin (Royal Holloway, U. London)
Title: Parameterized Combinatorial Optimization


We'll survey some results on well-known combinatorial optimization problems under various parameterizations. For example, the mixed chinese postman problem is fixed-parameter tractable when parameterized by the number of undirected edges, directed edges, or tree-depth of the underlying graph. Somewhat surprisingly, the problem is W[1]-hard when parameterized by the treewidth of the underlying graph. Among other problems, we'll consider the directed and undirected rural postman problems, and TSP.