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
- The non-essentials:
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-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.