Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

We study the robust communication complexity of maximum matching. Edges of an arbitrary n-vertex graph G are randomly partitioned between Alice and Bob independently and uniformly. Alice has to send a single message to Bob such that Bob can find an (approximate) maximum matching of the whole graph G. We specifically study the best approximation ratio achievable via protocols where Alice communicates only Õ(n) bits to Bob.
There has been a growing interest on the robust communication model due to its connections to the random-order streaming model. An algorithm of Assadi and Behnezhad [ICALP'21] implies a (2/3+ε₀ ∼ .667)-approximation for a small constant 0 < ε₀ < 10^{-18}, which remains the best-known approximation for general graphs. For bipartite graphs, Assadi and Behnezhad [Random'21] improved the approximation to .716 albeit with a computationally inefficient (i.e., exponential time) protocol.
In this paper, we study a natural and efficient protocol implied by a random-order streaming algorithm of Bernstein [ICALP'20] which is based on edge-degree constrained subgraphs (EDCS) [Bernstein and Stein; ICALP'15]. The result of Bernstein immediately implies that this protocol achieves an (almost) (2/3 ∼ .666)-approximation in the robust communication model. We present a new analysis, proving that it achieves a much better (almost) (5/6 ∼ .833)-approximation. This significantly improves previous approximations both for general and bipartite graphs. We also prove that our analysis of Bernstein’s protocol is tight.

Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{azarmehr_et_al:LIPIcs.ICALP.2023.14, author = {Azarmehr, Amir and Behnezhad, Soheil}, title = {{Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.14}, URN = {urn:nbn:de:0030-drops-180666}, doi = {10.4230/LIPIcs.ICALP.2023.14}, annote = {Keywords: Maximum Matching, Robust Communication Complexity, Edge Degree Constrained Subgraph} }

Document

RANDOM

**Published in:** LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

We study the robust - à la Chakrabarti, Cormode, and McGregor [STOC'08] - communication complexity of the maximum bipartite matching problem. The edges of an adversarially chosen n-vertex bipartite graph G are partitioned randomly between Alice and Bob. Alice has to send a single message to Bob, using which Bob has to output an approximate maximum matching of G. We are particularly interested in understanding the best approximation ratio possible by protocols that use a near-optimal message size of n ⋅ polylog(n).
The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA'12] gave a rac{2} {3}-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent random-order streaming algorithm of the authors [ICALP'21], uses O(n log n) communication to obtain a (rac{2} {3} + ε₀)-approximation for a constant ε₀ ∼ 10^{-14}. The best known lower bound, on the other hand, leaves open the possibility of all the way up to even a (1-ε)-approximation using near-linear communication for constant ε > 0.
In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distribution-dependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.

Sepehr Assadi and Soheil Behnezhad. On the Robust Communication Complexity of Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2021.48, author = {Assadi, Sepehr and Behnezhad, Soheil}, title = {{On the Robust Communication Complexity of Bipartite Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {48:1--48:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.48}, URN = {urn:nbn:de:0030-drops-147411}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.48}, annote = {Keywords: Maximum Matching, Communication Complexity, Random-Order Streaming} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G = (V, E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use O(n ⋅ polylog) space, and output a large matching of G.
We prove that for an absolute constant ε₀ > 0, one can find a (2/3 + ε₀)-approximate maximum matching of G using O(n log n) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3 + Ω(1))-approximation is achievable.

Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2021.19, author = {Assadi, Sepehr and Behnezhad, Soheil}, title = {{Beating Two-Thirds For Random-Order Streaming Matching}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.19}, URN = {urn:nbn:de:0030-drops-140887}, doi = {10.4230/LIPIcs.ICALP.2021.19}, annote = {Keywords: Maximum Matching, Streaming, Random-Order Streaming} }

Document

Brief Announcement

**Published in:** LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. In this paper, we revisit this problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:
Massively Parallel Computation. We give a randomized MPC algorithm that w.h.p., returns a (1+o(1))Delta edge coloring in O(1) rounds using O~(n) space per machine and O(m) total space. The space per machine can also be further improved to n^{1-Omega(1)} if Delta = n^{Omega(1)}. This is, to our knowledge, the first constant round algorithm for a natural graph problem in the strongly sublinear regime of MPC. Our algorithm improves a previous result of Harvey et al. [SPAA 2018] which required n^{1+Omega(1)} space to achieve the same result.
Graph Streaming. Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors.
We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors w.h.p., if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 36:1-36:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{behnezhad_et_al:LIPIcs.DISC.2019.36, author = {Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed}, title = {{Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {36:1--36:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.36}, URN = {urn:nbn:de:0030-drops-113438}, doi = {10.4230/LIPIcs.DISC.2019.36}, annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring} }

Document

**Published in:** LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, Delta, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:
- Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a Delta+O~(Delta^(3/4)) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^(1-Omega(1)) if Delta = n^Omega(1). Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018].
- Graph Streaming: Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors.
We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{behnezhad_et_al:LIPIcs.ESA.2019.15, author = {Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Knittel, Marina and Saleh, Hamed}, title = {{Streaming and Massively Parallel Algorithms for Edge Coloring}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.15}, URN = {urn:nbn:de:0030-drops-111361}, doi = {10.4230/LIPIcs.ESA.2019.15}, annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring} }

Document

Brief Announcement

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Solving large-scale graph problems is a fundamental task in many real-world applications, and it is an increasingly important problem in data analysis. Despite the large effort in designing scalable graph algorithms, many classic graph problems lack algorithms that require only a sublinear number of machines and space in the input size. Specifically when the input graph is large and sparse, which is indeed the case for many real-world graphs, it becomes impossible to store and access all the vertices in one machine - something that is often taken for granted in designing algorithms for massive graphs. The theoretical model that we consider is the Massively Parallel Communications (MPC) model which is a popular theoretical model of MapReduce-like systems. In this paper, we give an algorithmic framework to adapt a large family of dynamic programs on MPC. We start by introducing two classes of dynamic programming problems, namely "(poly log)-expressible" and "linear-expressible" problems. We show that both classes can be solved efficiently using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in O(log n) rounds of MPC, the dynamic programming solution of fundamental problems such as minimum bisection, k-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.

MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab Mirrokni. Brief Announcement: MapReduce Algorithms for Massive Trees. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 162:1-162:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bateni_et_al:LIPIcs.ICALP.2018.162, author = {Bateni, MohammadHossein and Behnezhad, Soheil and Derakhshan, Mahsa and Hajiaghayi, MohammadTaghi and Mirrokni, Vahab}, title = {{Brief Announcement: MapReduce Algorithms for Massive Trees}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {162:1--162:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.162}, URN = {urn:nbn:de:0030-drops-91666}, doi = {10.4230/LIPIcs.ICALP.2018.162}, annote = {Keywords: MapReduce, Trees} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail