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

Conference object English OPEN
Halldorsson , Magnus M. ; Konrad , Christian (2015)
  • Publisher: Springer-Verlag Berlin Heidelberg
  • Related identifiers: doi: 10.1007/978-3-662-48653-5_37
  • Subject: [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]

International audience; 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.
  • References (21)
    21 references, page 1 of 3

    1. Alon, N., Spencer, J.H.: The probabilistic method. John Wiley & Sons (2004)

    2. Barenboim, L.: On the locality of some NP-complete problems. In: Proc.of International Colloquium on Automata, Languages, and Programming, ICALP'12 (2). pp. 403{415 (2012)

    3. Caro, Y.: New results on the independence number. Tech. rep., Tel Aviv University (1979)

    4. Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Proceedings of the 24th International Conference on Distributed Computing. pp. 148{162. DISC'10, Springer-Verlag, Berlin, Heidelberg (2010), http://dl.acm.org/citation.cfm?id=1888781.1888802

    5. Czygrinow, A., Hanckowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proceedings of the 22Nd International Symposium on Distributed Computing. pp. 78{92. DISC '08, Springer-Verlag, Berlin, Heidelberg (2008)

    6. Halldorsson, B.V., Halldorsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets. In: Abramsky, S., Gavoille, C., Kirchner, C., auf der Heide, F.M., Spirakis, P.G. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 6198, pp. 641{652. Springer (2010)

    7. Halldorsson, M.M.: Wireless scheduling with power control. ACM Trans. Algorithms 9(1), 7:1{7:20 (Dec 2012)

    8. Halldorsson, M.M., Konrad, C.: Distributed algorithms for coloring interval graphs. In: Proceedings of the 28th International Conference on Distributed Computing. DISC'14 (2014)

    9. Halldorsson, M.M., Mitra, P.: Nearly optimal bounds for distributed wireless scheduling in the SINR model. In: Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II. pp. 625{636. ICALP'11, Springer-Verlag, Berlin, Heidelberg (2011), http://dl.acm.org/citation.cfm?id=2027223.2027287

    10. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85{103. Plenum Press (1972)

  • Similar Research Results (2)
  • Metrics
    No metrics available
Share - Bookmark