After wading through a torrent of submissions, the ICALP programme committee released the final list of accepted papers this week. There are 126 in total, 70 in track A (last year: 76 and 41). It looks like over 20 papers a day are going to be jostling for attention in multiple parallel sessions.

A paper I found interesting is

This paper claims to be the first practical implementation of linear time modular decomposition, which is used as a building block by many efficient graph algorithms. Jens Gustedt pointed out a few years ago that the Ehrenfeucht et al. algorithm from 1994 seems to have runtime , which is slightly worse than linear. This certainly has been implemented, although I’m unsure if the bound Jens suggested is achieved by this code; Ross McConnell also mentioned a previous implementation (lost in the mists of time). Implementing the 1994 algorithm involves some fairly nontrivial bits, mostly in reconstructing missing `obvious’ details. I am therefore looking forward to reading the paper in detail — it would be nice to have an algorithm that can be implemented, and that still achieves linear runtime.

## STOC 2008

Tags: conferences, papers

A quick rundown of some of the more interesting papers.

Barto, Kozik, Niven: Graphs, polymorphisms and the complexity of homomorphism problems

This paper shows (Theorem 3.1) that if a digraph without sources and sinks admits a weak near unanimity operation, then it retracts onto a disjoint union of circles [a circle is an induced directed cycle]. They also claim to have a more general version in preparation, for relational structures. This result can then be used to prove the Bang-Jensen/Hell conjecture, that for finite digraphs

Hwithout sinks or sources, if each component of the core ofHis a circle, thenH-colourability is in PTIME, otherwise it is NP-complete.Rossman: On the constant-depth complexity of

k-cliqueThis shows (Corollary 1.4) that no sentence in first-order logic with at most

k/4variables can expressk-clique on the class of finite ordered graphs. Rossman claims the full version will show that this holds for the class of finite graphs with arbitrary numerical predicates also. This means (Corollaries 1.5 and 1.7) that the bounded variable hierarchy on finite ordered graphs is non-collapsing and strict; previously it was not known if 3 variables was enough to express every FO formula on finite ordered graphs. Moreover, Theorem 1.2 says that for everyk, thek-clique problem onn-vertex graphs requires constant-depth circuits of asymptotic size at least .Frieze, Vempala, Vera: Logconcave random graphs

This generalizes the usual Erdős-Rényi model of a random graph to a two stage process, where first a multivariate distribution determines a random point in an -dimensional cube, then a threshold

pis used to determine whether the edge corresponding to each direction is present or not. The usual random graph model with uniform edge probabilities is then the special case of a uniform distribution over the unit cube. The paper works with a logconcave distribution, and they point out (Open question 5.1) that special cases capture graph classes such as triangle-free, by defining the distribution in terms of the solutions of a linear program. They ask whetherH-free graphs can be “uniformly” generated this way.