Second & third week

The second week I was still mostly reading up on the background of what I am studying. As I mentioned previously, there is a beautiful new result by Michail Lampis on \(MSO_1\) model checking lower bounds for simple graphs (such as paths) which, as a corollary, contains the hardness result for cliques I was looking for (basically saying \(MSO_2\) model checking on cliques is not even in XP).

The idea of the result is actually simple enough for me to sum it up here. We want to prove that deciding some \(MSO_1\) -definable properties is hard already on paths. These are just about the simplest structures one can get -- their only distinguishable property is their length. The complexity assumption we're using for our proof is something a bit weaker than the usual \(P \neq NP\) -- this time we're assuming that \(P_1 \neq NP_1\) (where \(P_1\) and \(NP_1\) are the classes of unary languages decidable in polynomial deterministic / non-deterministic time). This assumption is equivalent to \(EXP \neq NEXP\) . For example assume that \(P_1 = NP_1\) -- then we can unary-code any language \(L \in NEXP\) with at most exponential blow-up and since this new \(L_{exp}\) is unary, we have \(L_{exp} \in NP_1 = P_1\) and thus \(L \in EXP\) .

What Lampis does in his paper then is to show that the rules for a computation of a Turing machine can be encoded in a \(MSO_1\) sentence and this computation can be carried out in unary. It was previously known that if we allow labelled paths (e.g. every vertex is either black or white, encoding zeros and ones), paths can be viewed as computations. The new result in Lampis' paper is that it can also be done in unary. To achieve this Lampis had to show the existence of some very concise formulas to compare the length of path segments; the described construction is interesting in itself.

But the theorem I was looking for is not concerned with paths (remember that graphs with bounded neighborhood diversity have bounded diameter); it talks about the complexity of \(MSO_2\) (that is, formulas containing edge set quantifiers) model checking. But that follows from the theorem above easily: take an arbitrarily big clique and preface the formula with an \(\exists P \subseteq E, \varphi_{\text{path}}(P)\) , where \(\varphi_{\text{path}}(P)\) is a FO formula assuring that \(P\) is a path. Now use the previously described result.

Thus the answer is: yes, there is a \(MSO_2\) definable problem, which is hard (not even XP) already on cliques. But is that really what we care about? How many natural problems model the computation of a Turing machine? This remains an open question for us: is there a natural W[1]-hard problem on graphs with bounded neighborhood diversity when only the graph is the input? Also, Lampis' result seems to be more of an evidence that \(MSO\) logics are way stronger than we need in most cases, rather than paths or cliques being complicated graphs. Perhaps there are other logics that behave more nicely? Recent paper by Michał Pilipczuk seems to be going in that direction (but with regard to treewidth). So we have some cues, but no specific results yet.

The rest of my time was dedicated to the study of shrub-depth, a parameter generalizing neighborhood diversity. A fair amount of time was consumed merely by getting familiar and comfortable with the definitions, which I finally can claim to be. The goal I am trying to achieve now is to generalize the coloring algorithm for graphs of bounded neighborhood diversity to graphs of bounded shrub-depth, specifically (to make matters simple) of shrub-depth 2.

I would like to explain the motivation in a bit more detail. The hierarchy of discussed parameters is such that clique-width is the most general and vertex cover is the most restrictive. The coloring problem is W[1]-hard on graphs of bounded clique-width -- but is FPT on graphs with bounded tree-width, which lies under clique-width, but is incomparable with shrub-depth and neighborhood diversity. Shrub-depth can be seen as forming a finer hierarchy between vertex-cover and clique-width (omitting some details). If coloring is hard for clique-width, but easy for tree-width and neighborhood diversity, where does shrub-depth fall in? In other words, where do things break -- when we go from neighborhood diversity to shrub-depth, or when we go from shrub-depth to clique-width?

To that end I have made some observations, but again, no definitive result yet.

It is worth mentioning that we spend the last three days in Princeton visiting a Spectral Methods mini-course. I have to say that Princeton is a beautiful place well worth seeing; the mini-course had its ups and downs, but overall I've enjoyed it (as did the rest of our group).

That's it for now. Wish me luck.