Henning Hasemann · Juho Hirvonen · Joel Rybicki · Jukka Suomela

Deterministic local algorithms, unique identifiers, and fractional graph colouring

SIROCCO 2012 · 19th International Colloquium on Structural Information and Communication Complexity, Reykjavík, Iceland, June–July 2012 · doi:10.1007/978-3-642-31104-8_5

authors’ version publisher’s version


We show that for any α > 1 there exists a deterministic distributed algorithm that finds a fractional graph colouring of length at most α(∆ + 1) in any graph in one synchronous communication round; here ∆ is the maximum degree of the graph. The result is near-tight, as there are graphs in which the optimal solution has length ∆ + 1.

The result is, of course, too good to be true. The usual definitions of scheduling problems (fractional graph colouring, fractional domatic partition, etc.) in a distributed setting leave a loophole that can be exploited in the design of distributed algorithms: the size of the local output is not bounded. Our algorithm produces an output that seems to be perfectly good by the usual standards but it is impractical, as the schedule of each node consists of a very large number of short periods of activity.

More generally, the algorithm shows that when we study distributed algorithms for scheduling problems, we can choose virtually any trade-off between the following three parameters: T, the running time of the algorithm, l, the length of the schedule, and κ, the maximum number of periods of activity for any single node. Here l is the objective function of the optimisation problem, while κ captures the “subjective” quality of the solution. If we study, for example, bounded-degree graphs, we can trivially keep T and κ constant, at the cost of a large l, or we can keep κ and l constant, at the cost of a large T. Our algorithm shows that yet another trade-off is possible: we can keep T and l constant at the cost of a large κ.


Guy Even and Magnús M. Halldórsson (Eds.): Structural Information and Communication Complexity, 19th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30 – July 2, 2012, Proceedings, volume 7355 of Lecture Notes in Computer Science, pages 48–60, Springer, Berlin, 2012

ISBN 978-3-642-31103-1


Journal Version

© Springer 2012 — The original publication is available at www.springerlink.com.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.