Constraints

2 June 2008

STOC 2008

Filed under: Commentary — András Salamon @ 20:32
Tags: ,

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 H without sinks or sources, if each component of the core of H is a circle, then H-colourability is in PTIME, otherwise it is NP-complete.

Rossman: On the constant-depth complexity of k-clique

This shows (Corollary 1.4) that no sentence in first-order logic with at most k/4 variables can express k-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 every k, the k-clique problem on n-vertex graphs requires constant-depth circuits of asymptotic size at least $n^{k/4 + o(1)}$.

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 $n(n-1)/2$-dimensional cube, then a threshold p is 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 whether H-free graphs can be “uniformly” generated this way.