Distributed symmetry breaking in hypergraphs

Shay Kutten; Danupon Nanongkai; Gopal Pandurangan; Peter Robinson

doi:10.1007/978-3-662-45174-8_32

Distributed symmetry breaking in hypergraphs

Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

Abstract

Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.

In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in O(log²n) rounds (n is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper — an O(Δ^∈polylog n)-round hypergraph MIS algorithm in the CONGEST model where Δ is the maximum node degree of the hypergraph and ∈ >0 is any arbitrarily small constant. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.

To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the balanced minimal dominating set problem (left open in Harris et al. [ICALP 2013]) and the minimal connected dominating set problem.

Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.

Original language	English (US)
Title of host publication	Distributed Computing - 28th International Symposium, DISC 2014, Proceedings
Editors	Fabian Kuhn
Publisher	Springer Verlag
Pages	469-483
Number of pages	15
ISBN (Electronic)	9783662451731
DOIs	https://doi.org/10.1007/978-3-662-45174-8_32
State	Published - 2014
Externally published	Yes
Event	28th International Symposium on Distributed Computing, DISC 2014 - Austin, United States Duration: Oct 12 2014 → Oct 15 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8784
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Symposium on Distributed Computing, DISC 2014
Country/Territory	United States
City	Austin
Period	10/12/14 → 10/15/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-45174-8_32

Cite this

Kutten, S., Nanongkai, D., Pandurangan, G., & Robinson, P. (2014). Distributed symmetry breaking in hypergraphs. In F. Kuhn (Ed.), Distributed Computing - 28th International Symposium, DISC 2014, Proceedings (pp. 469-483). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8784). Springer Verlag. https://doi.org/10.1007/978-3-662-45174-8_32

Distributed symmetry breaking in hypergraphs. / Kutten, Shay; Nanongkai, Danupon; Pandurangan, Gopal et al.
Distributed Computing - 28th International Symposium, DISC 2014, Proceedings. ed. / Fabian Kuhn. Springer Verlag, 2014. p. 469-483 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8784).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kutten, S, Nanongkai, D, Pandurangan, G & Robinson, P 2014, Distributed symmetry breaking in hypergraphs. in F Kuhn (ed.), Distributed Computing - 28th International Symposium, DISC 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8784, Springer Verlag, pp. 469-483, 28th International Symposium on Distributed Computing, DISC 2014, Austin, United States, 10/12/14. https://doi.org/10.1007/978-3-662-45174-8_32

Kutten S, Nanongkai D, Pandurangan G, Robinson P. Distributed symmetry breaking in hypergraphs. In Kuhn F, editor, Distributed Computing - 28th International Symposium, DISC 2014, Proceedings. Springer Verlag. 2014. p. 469-483. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-45174-8_32

Kutten, Shay ; Nanongkai, Danupon ; Pandurangan, Gopal et al. / Distributed symmetry breaking in hypergraphs. Distributed Computing - 28th International Symposium, DISC 2014, Proceedings. editor / Fabian Kuhn. Springer Verlag, 2014. pp. 469-483 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2687998cab574a968f45310b703ef6e0,

title = "Distributed symmetry breaking in hypergraphs",

abstract = "Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in O(log2n) rounds (n is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper — an O(Δ∈polylog n)-round hypergraph MIS algorithm in the CONGEST model where Δ is the maximum node degree of the hypergraph and ∈ >0 is any arbitrarily small constant. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the balanced minimal dominating set problem (left open in Harris et al. [ICALP 2013]) and the minimal connected dominating set problem.Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.",

author = "Shay Kutten and Danupon Nanongkai and Gopal Pandurangan and Peter Robinson",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2014.; 28th International Symposium on Distributed Computing, DISC 2014 ; Conference date: 12-10-2014 Through 15-10-2014",

year = "2014",

doi = "10.1007/978-3-662-45174-8_32",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "469--483",

editor = "Fabian Kuhn",

booktitle = "Distributed Computing - 28th International Symposium, DISC 2014, Proceedings",

}

TY - GEN

T1 - Distributed symmetry breaking in hypergraphs

AU - Kutten, Shay

AU - Nanongkai, Danupon

AU - Pandurangan, Gopal

AU - Robinson, Peter

PY - 2014

Y1 - 2014

N2 - Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in O(log2n) rounds (n is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper — an O(Δ∈polylog n)-round hypergraph MIS algorithm in the CONGEST model where Δ is the maximum node degree of the hypergraph and ∈ >0 is any arbitrarily small constant. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the balanced minimal dominating set problem (left open in Harris et al. [ICALP 2013]) and the minimal connected dominating set problem.Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.

AB - Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs.In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in O(log2n) rounds (n is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper — an O(Δ∈polylog n)-round hypergraph MIS algorithm in the CONGEST model where Δ is the maximum node degree of the hypergraph and ∈ >0 is any arbitrarily small constant. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the balanced minimal dominating set problem (left open in Harris et al. [ICALP 2013]) and the minimal connected dominating set problem.Our work shows that while some local symmetry breaking problems such as coloring can be solved in polylogarithmic rounds in both the LOCAL and CONGEST models, for many other hypergraph problems such as MIS, hitting set, and maximal clique, it remains challenging to obtain polylogarithmic time algorithms in the CONGEST model. This work is a step towards understanding this dichotomy in the complexity of hypergraph problems as well as using hypergraphs to design fast distributed algorithms for problems in (standard) graphs.

UR - http://www.scopus.com/inward/record.url?scp=84910628097&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84910628097&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-45174-8_32

DO - 10.1007/978-3-662-45174-8_32

M3 - Conference contribution

AN - SCOPUS:84910628097

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 469

EP - 483

BT - Distributed Computing - 28th International Symposium, DISC 2014, Proceedings

A2 - Kuhn, Fabian

PB - Springer Verlag

T2 - 28th International Symposium on Distributed Computing, DISC 2014

Y2 - 12 October 2014 through 15 October 2014

ER -

Distributed symmetry breaking in hypergraphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this