Distributed Large Independent Sets in One Round On Bounded-independence Graphs - DIStributed Computing 2015 Access content directly
Conference Papers Year : 2015

Distributed Large Independent Sets in One Round On Bounded-independence Graphs

Abstract

We present a randomized one-round, single-bit messages, distributed algorithm for the maximum independent set problem in polynomially bounded-independence graphs with poly-logarithmic approximation factor. Bounded-independence graphs capture various models of wireless networks such as the unit disc graphs model and the quasi unit disc graphs model. For instance, on unit disc graphs, our achieved approximation ratio is O((log(n)/log(log(n)))^2). A starting point of our work is an extension of Turan’s bound for independent sets by Caro and Wei which states that every graph G = (V, E) contains an independent set of size at least β(G):=sum{v∈V}1/(degG(v)+1) where degG(v) denotes the degree of v in G. Alon and Spencer’s proof of the Caro-Wei bound in [1] suggests a randomized distributed one-round algorithm that outputs an independent set of expected size equal to β(G), using messages of sizes O(log n), where n is the number of vertices of the input graph. To achieve our main result, we show that β(G) gives poly-logarithmic approximation ratios for polynomially bounded- independence graphs. Then, for O(1)-claw free graphs (which include graphs of bounded-independence), we show that using a different algorithm, an independent set of expected size Θ(β(G)) can be computed in one round using single bit messages, thus reducing the communication cost to an absolute minimum. Last, in general graphs, β(G) may only give an Ω(n)-approximation. We show, however, that this is best possible for one-round algorithms: We show that each such distributed algorithm (possibly randomized) has an approximation ratio of Ω(n) on general graphs.
Fichier principal
Vignette du fichier
51.pdf (381.29 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01207829 , version 1 (01-10-2015)

Identifiers

Cite

Magnus M. Halldorsson, Christian Konrad. Distributed Large Independent Sets in One Round On Bounded-independence Graphs. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_37⟩. ⟨hal-01207829⟩

Collections

DISC2015
53 View
227 Download

Altmetric

Share

Gmail Facebook X LinkedIn More