Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1+ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [Manoj Gupta and Richard Peng, 2013]) gave an algorithm for this problem with an update time of O(√m/ε²).
Motivated by the fact that the O_ε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [Henzinger et al., 2015]; Kopelowitz, Pettie, and Porat [Kopelowitz et al., 2016]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [Bernstein et al., 2020]) gave an O(poly({log n}/ε)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs.
In this paper, we bridge the gap between bipartite and general graphs, by giving an O_ε(poly(log n)) update time algorithm that maintains a (1+ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [Fabrizio Grandoni et al., 2019] who give an O_ε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.

Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }

Document

**Published in:** LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

The goal of this paper is to understand the complexity of a key symmetry breaking problem, namely the (α,β)-ruling set problem in the graph streaming model. Given a graph G = (V,E), an (α, β)-ruling set is a subset I ⊆ V such that the distance between any two vertices in I is at least α and the distance between a vertex in V and the closest vertex in I is at most β. This is a fundamental problem in distributed computing where it finds applications as a useful subroutine for other problems such as maximal matching, distributed colouring, or shortest paths. Additionally, it is a generalization of MIS, which is a (2,1)-ruling set.
Our main results are two algorithms for (2,2)-ruling sets:
1) In adversarial streams, where the order in which edges arrive is arbitrary, we give an algorithm with Õ(n^{4/3}) space, improving upon the best known algorithm due to Konrad et al. [DISC 2019], with space Õ(n^{3/2}).
2) In random-order streams, where the edges arrive in a random order, we give a semi-streaming algorithm, that is an algorithm that takes Õ(n) space. Finally, we present new algorithms and lower bounds for (α,β)-ruling sets for other values of α and β. Our algorithms improve and generalize the previous work of Konrad et al. [DISC 2019] for (2,β)-ruling sets, while our lower bound establishes the impossibility of obtaining any non-trivial streaming algorithm for (α,α-1)-ruling sets for all even α > 2.

Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.DISC.2021.6, author = {Assadi, Sepehr and Dudeja, Aditi}, title = {{Ruling Sets in Random Order and Adversarial Streams}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.6}, URN = {urn:nbn:de:0030-drops-148086}, doi = {10.4230/LIPIcs.DISC.2021.6}, annote = {Keywords: Symmetry breaking, Ruling sets, Lower bounds, Communication Complexity} }

Document

**Published in:** LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

In the incremental cycle detection problem, edges are added to a directed graph (initially empty), and the algorithm has to report the presence of the first cycle, once it is formed. A closely related problem is the incremental topological sort problem, where edges are added to an acyclic graph, and the algorithm is required to maintain a valid topological ordering. Since these problems arise naturally in many applications such as scheduling tasks, pointer analysis, and circuit evaluation, they have been studied extensively in the last three decades. Motivated by the fact that in many of these applications, the presence of a cycle is not fatal, we study a generalization of these problems, incremental maintenance of strongly connected components (incremental SCC).
Several incremental algorithms in the literature which do cycle detection and topological sort in directed acyclic graphs, such as those by [Michael A. Bender et al., 2016] and [Haeupler et al., 2012], also generalize to maintain strongly connected components and their topological sort in general directed graphs. The algorithms of [Haeupler et al., 2012] and [Michael A. Bender et al., 2016] have a total update time of O(m^{3/2}) and O(m⋅ min{m^{1/2},n^{2/3}}) respectively, and this is the state of the art for incremental SCC. But the most recent algorithms for incremental cycle detection and topological sort ([Bernstein and Chechik, 2018] and [Bhattacharya and Kulkarni, 2020]), which yield total (randomized) update time Õ(min{m^{4/3}, n²}), do not extend to incremental SCC. Thus, there is a gap between the best known algorithms for these two closely related problems.
In this paper, we bridge this gap by extending the framework of [Bhattacharya and Kulkarni, 2020] to general directed graphs. More concretely, we give a Las Vegas algorithm for incremental SCCs with an expected total update time of Õ(m^{4/3}). A key ingredient in the algorithm of [Bhattacharya and Kulkarni, 2020] is a structural theorem (first introduced in [Bernstein and Chechik, 2018]) that bounds the number of "equivalent" vertices. Unfortunately, this theorem only applies to DAGs. We show a natural way to extend this structural theorem to general directed graphs, and along the way we develop a significantly simpler and more intuitive proof of this theorem.

Aaron Bernstein, Aditi Dudeja, and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.ESA.2021.14, author = {Bernstein, Aaron and Dudeja, Aditi and Pettie, Seth}, title = {{Incremental SCC Maintenance in Sparse Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.14}, URN = {urn:nbn:de:0030-drops-145950}, doi = {10.4230/LIPIcs.ESA.2021.14}, annote = {Keywords: Directed Graphs, Strongly Connected Components, Dynamic Graph Algorithms} }

Document

**Published in:** LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

The matching problem in the online setting models the following situation: we are given a set of servers in advance, the clients arrive one at a time, and each client has edges to some of the servers. Each client must be matched to some incident server upon arrival (or left unmatched) and the algorithm is not allowed to reverse its decisions. Due to this no-reversal restriction, we are not able to guarantee an exact maximum matching in this model, only an approximate one.
Therefore, it is natural to study a different setting, where the top priority is to match as many clients as possible, and changes to the matching are possible but expensive. Formally, the goal is to always maintain a maximum matching while minimizing the number of changes made to the matching (denoted the recourse). This model is called the online model with recourse, and has been studied extensively over the past few years. For the specific problem of matching, the focus has been on vertex-arrival model, where clients arrive one at a time with all their edges. A recent result of Bernstein et al. [Bernstein et al., 2019] gives an upper bound of O (nlog² n) recourse for the case of general bipartite graphs. For trees the best known bound is O(nlog n) recourse, due to Bosek et al. [Bosek et al., 2018]. These are nearly tight, as a lower bound of Ω(nlog n) is known.
In this paper, we consider the more general model where all the vertices are known in advance, but the edges of the graph are revealed one at a time. Even for the simple case where the graph is a path, there is a lower bound of Ω(n²). Therefore, we instead consider the natural relaxation where the graph is worst-case, but the edges are revealed in a random order. This relaxation is motivated by the fact that in many related models, such as the streaming setting or the standard online setting without recourse, faster algorithms have been obtained for the matching problem when the input comes in a random order. Our results are as follows:
- Our main result is that for the case of general (non-bipartite) graphs, the problem with random edge arrivals is almost as hard as in the adversarial setting: we show a family of graphs for which the expected recourse is Ω(n²/log n).
- We show that for some special cases of graphs, random arrival is significantly easier. For the case of trees, we get an upper bound of O(nlog²n) on the expected recourse. For the case of paths, this upper bound is O(nlog n). We also show that the latter bound is tight, i.e. that the expected recourse is at least Ω(nlog n).

Aaron Bernstein and Aditi Dudeja. Online Matching with Recourse: Random Edge Arrivals. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 11:1-11:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bernstein_et_al:LIPIcs.FSTTCS.2020.11, author = {Bernstein, Aaron and Dudeja, Aditi}, title = {{Online Matching with Recourse: Random Edge Arrivals}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.11}, URN = {urn:nbn:de:0030-drops-132521}, doi = {10.4230/LIPIcs.FSTTCS.2020.11}, annote = {Keywords: matchings, edge-arrival, online model} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail