About Me

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

Me in a picture

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:

Have a look at my first presentation.