## Combinatorics Seminar

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

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.