Most of the first week was consumed by recovering from jet-lag,
finding our way around the campus and after that all figuring out what
to focus on exactly. Out of many attractive options I selected to
follow up on the subject of my master thesis (excerpts, the whole pdf), a graph parameter called
*neighborhood diversity*.

For now what that means for me is getting deeper into the technicalities of papers I knew existed but which I understood only superficially.

For example, graphs with neighborhood diversity \(k\)
only take \(O(k^3
log(n))\)
bits to encode. What can we do with that? Well, it means that
any problem defined over them is a sparse language and Mahaney's
theorem
says, that if some sparse language was NP-complete, then
EXP=NEXP. What can we do with *that*?

Second, what are some possibly hard problems for graphs with bounded
neighborhood diversity? Courcelle, Makowski and Rotics
[CourcelleMR00] show that \(MSO_2\)
model checking cannot be FPT
already on cliques unless EXP=NEXP (see the connection with the
above?). But the proof is very *sparse* (pun intended) and refers to old
results by Ronald Fagin [Fagin75] which are hard to
*parse*. Fortunately, there are some nice new results [Lampis13] by Michail Lampis and
as a corollary the result I was looking for is also proved!

Third, in what ways could I extend my positive results? Perhaps there is a parameter that generalizes neighborhood diversity...? And indeed there is: shrub-depth. It was introduced by Ganian et al. [GanianHNOMR12], then some more work was done on it by Gajarský and Hliněný [GajarskyH12]. That's a lot of reading.

Well, I'm excited to find where this gets me, but so far I have no definitive results I could report, just hunches I will try to chase in the following weeks. Stay tuned.

[CourcelleMR00] | Courcelle, Makowsky, Rotics 2000: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width |

[Fagin75] | Fagin 1975: A spectrum hierarchy |

[Lampis13] | Lampis 2013: Model Checking Lower Bounds for Simple Graphs |

[GanianHNOMR12] | Ganian, Hliněný, Nešetřil, de Mendez, Ramadurai 2012: When Trees Grow Low: Shrubs and Fast MSO1. |

[GajarskyH12] | Gajarský, Hliněný 2012: Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences. |