Node and edge averaged complexities of local graph problems
Abstract We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $$G=(V,E)$$...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151070 |
| _version_ | 1810992359021740032 |
|---|---|
| author | Balliu, Alkida Ghaffari, Mohsen Kuhn, Fabian Olivetti, Dennis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Balliu, Alkida Ghaffari, Mohsen Kuhn, Fabian Olivetti, Dennis |
| author_sort | Balliu, Alkida |
| collection | MIT |
| description | Abstract
We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph
$$G=(V,E)$$
G
=
(
V
,
E
)
is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree
$$\Delta $$
Δ
is at least
$$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$
Ω
(
min
{
log
Δ
log
log
Δ
,
log
n
log
log
n
}
)
. This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM’16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also
$$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$
Ω
(
min
{
log
Δ
log
log
Δ
,
log
n
log
log
n
}
)
—this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an
$$O(\sqrt{\log \log n})$$
O
(
log
log
n
)
factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O(1). For maximal matching, we show that while the randomized node-averaged complexity is
$$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$
Ω
(
min
{
log
Δ
log
log
Δ
,
log
n
log
log
n
}
)
, the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is
$$O(\log ^2\Delta + \log ^* n)$$
O
(
log
2
Δ
+
log
∗
n
)
and the deterministic node-averaged complexity of maximal matching is
$$O(\log ^3\Delta + \log ^* n)$$
O
(
log
3
Δ
+
log
∗
n
)
. Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be
$$\Theta (\log n)$$
Θ
(
log
n
)
, even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity
$$O(\log ^* n)$$
O
(
log
∗
n
)
, while keeping the worst-case complexity in
$$O(\log n)$$
O
(
log
n
)
. |
| first_indexed | 2024-09-23T13:08:19Z |
| format | Article |
| id | mit-1721.1/151070 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:08:19Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1510702024-01-31T20:44:35Z Node and edge averaged complexities of local graph problems Balliu, Alkida Ghaffari, Mohsen Kuhn, Fabian Olivetti, Dennis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abstract We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $$G=(V,E)$$ G = ( V , E ) is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree $$\Delta $$ Δ is at least $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω ( min { log Δ log log Δ , log n log log n } ) . This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM’16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω ( min { log Δ log log Δ , log n log log n } ) —this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an $$O(\sqrt{\log \log n})$$ O ( log log n ) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O(1). For maximal matching, we show that while the randomized node-averaged complexity is $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω ( min { log Δ log log Δ , log n log log n } ) , the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is $$O(\log ^2\Delta + \log ^* n)$$ O ( log 2 Δ + log ∗ n ) and the deterministic node-averaged complexity of maximal matching is $$O(\log ^3\Delta + \log ^* n)$$ O ( log 3 Δ + log ∗ n ) . Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be $$\Theta (\log n)$$ Θ ( log n ) , even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity $$O(\log ^* n)$$ O ( log ∗ n ) , while keeping the worst-case complexity in $$O(\log n)$$ O ( log n ) . 2023-07-10T18:51:14Z 2023-07-10T18:51:14Z 2023-07-05 2023-07-09T03:17:23Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151070 Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian and Olivetti, Dennis. 2023. "Node and edge averaged complexities of local graph problems." PUBLISHER_CC en https://doi.org/10.1007/s00446-023-00453-1 Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Balliu, Alkida Ghaffari, Mohsen Kuhn, Fabian Olivetti, Dennis Node and edge averaged complexities of local graph problems |
| title | Node and edge averaged complexities of local graph problems |
| title_full | Node and edge averaged complexities of local graph problems |
| title_fullStr | Node and edge averaged complexities of local graph problems |
| title_full_unstemmed | Node and edge averaged complexities of local graph problems |
| title_short | Node and edge averaged complexities of local graph problems |
| title_sort | node and edge averaged complexities of local graph problems |
| url | https://hdl.handle.net/1721.1/151070 |
| work_keys_str_mv | AT balliualkida nodeandedgeaveragedcomplexitiesoflocalgraphproblems AT ghaffarimohsen nodeandedgeaveragedcomplexitiesoflocalgraphproblems AT kuhnfabian nodeandedgeaveragedcomplexitiesoflocalgraphproblems AT olivettidennis nodeandedgeaveragedcomplexitiesoflocalgraphproblems |