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.


14 April 2008

ICALP 2008 accepted papers

Filed under: Commentary — András Salamon @ 14:52
Tags: ,

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

Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul. Simple, Linear-Time Modular Decomposition

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 \min(n^2,m \log n), 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.

« Previous Page

Blog at