First week

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.