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 |

[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. |