# About Me

**To read about how my project is progressing, see the** blog.

*The essentials:***Martin Koutecký**- Office @ CORE 450
- Faculty of Mathematics and Physics, Charles University in Prague
- martin@koutecky.name

*The non-essentials:*- I am interested in Parameterized Complexity, Approximation algorithms and Combinatorial optimization in general.
- I like to bike, read, drink Czech beer and play the violin.

## Hardness boundary for neighborhood diversity

My project is related to my master thesis (excerpts, the whole pdf) which deals with a recently introduced graph parameter called neighborhood diversity. To get an idea as to what parameterized complexity is and why this new parameter might be significant, take a look at the some excerpts from the thesis.

Neighborhood diversity is very easy to
work with. As such, many problems which are hard with respect to
treewidth (*Complete coloring*, *Equitable coloring* or *Capacitated
dominating set* and others) were proven to be
fixed-parameter tractable with respect to neighborhood
diversity. Moreover, *all* significant results (except for \(MSO_1\)
model
checking) for ND were proven using a result of Lenstra, which says
that Integer Linear Programming (ILP) is FPT in fixed dimension. My
questions which follow from that are the following:

- What is the
*hardness boundary*for neighborhood diversity, that is, which are (in whatever sense) the hardest problems that are still FPT w.r.t. ND, and which are the easiest problems that are already W[1]-hard w.r.t. ND? - Is there a way to formalize or generalize the fact that ILP is such an effective technique with these graphs? (In a similar spirit as Courcelle's Theorem formalizes that dynamic programming is an effective technique for graphs of bounded treewidth)

Have a look at my first presentation.