Narrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions.
Saved in:
| Title: | Narrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions. |
|---|---|
| Authors: | Chang, Yi-Jun1 (AUTHOR) cyijun@nus.edu.sg, Su, Hsin-Hao2 (AUTHOR) hsinhao.su@bc.edu |
| Source: | Distributed Computing. Jun2026, Vol. 39 Issue 2, p1-34. 34p. |
| Subjects: | Sparse graphs, Combinatorial optimization, Graph theory, Distributed algorithms |
| Abstract: | Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within factors in rounds in the model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic model, which restricts the message size to be bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an -approximate maximum weighted matching can be computed in rounds in the model. In this paper, we develop a generic framework for obtaining -round -approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs. Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & Distributed Computing 2021]. Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a vertex. Similar to the use of network decompositions in the model, the vertex will be able to perform any local computation on the subgraph induced by the cluster and broadcast the result over the cluster. [ABSTRACT FROM AUTHOR] |
| Copyright of Distributed Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| Abstract: | Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within factors in rounds in the model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic model, which restricts the message size to be bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an -approximate maximum weighted matching can be computed in rounds in the model. In this paper, we develop a generic framework for obtaining -round -approximation algorithms for many combinatorial optimization problems, including maximum weighted matching, maximum independent set, and correlation clustering, in graphs excluding a fixed minor in the model. This class of graphs covers many sparse network classes that have been studied in the literature, including planar graphs, bounded-genus graphs, and bounded-treewidth graphs. Furthermore, we show that our framework can be applied to give an efficient distributed property testing algorithm for an arbitrary minor-closed graph property that is closed under taking disjoint union, significantly generalizing the previous distributed property testing algorithm for planarity in [Levi, Medina, and Ron, PODC 2018 & Distributed Computing 2021]. Our framework uses distributed expander decomposition algorithms [Chang and Saranurak, FOCS 2020] to decompose the graph into clusters of high conductance. We show that any graph excluding a fixed minor admits small edge separators. Using this result, we show the existence of a high-degree vertex in each cluster in an expander decomposition, which allows the entire graph topology of the cluster to be routed to a vertex. Similar to the use of network decompositions in the model, the vertex will be able to perform any local computation on the subgraph induced by the cluster and broadcast the result over the cluster. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01782770 |
| DOI: | 10.1007/s00446-025-00496-6 |
