On the locality of some NP-complete problems
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20)
Abstract: We consider the distributed message-passing {LOCAL} model. In this model a communication network is represented by a graph where vertices host processors, and communication is performed over the edges. Computation proceeds in synchronous rounds. The running time of an algorithm is the number of rounds from the beginning until all vertices terminate. Local computation is free. An algorithm is called {local} if it terminates within a constant number of rounds. The question of what problems can be computed locally was raised by Naor and Stockmayer cite{NS93} in their seminal paper in STOC'93. Since then the quest for problems with local algorithms, and for problems that cannot be computed locally, has become a central research direction in the field of distributed algorithms cite{KMW04,KMW10,LOW08,PR01}. We devise the first local algorithm for an {NP-complete} problem. Specifically, our randomized algorithm computes, with high probability, an O(n^{1/2 + epsilon} cdot chi)-coloring within O(1) rounds, where epsilon > 0 is an arbitrarily small constant, and chi is the chromatic number of the input graph. (This problem was shown to be NP-complete in cite{Z07}.) On our way to this result we devise a constant-time algorithm for computing (O(1), O(n^{1/2 + epsilon}))-network-decompositions. Network-decompositions were introduced by Awerbuch et al. cite{AGLP89}, and are very useful for solving various distributed problems. The best previously-known algorithm for network-decomposition has a polylogarithmic running time (but is applicable for a wider range of parameters) cite{LS93}. We also devise a Delta^{1 + epsilon}-coloring algorithm for graphs with sufficiently large maximum degree Delta that runs within O(1) rounds. It improves the best previously-known result for this family of graphs, which is O(log-star n) cite{SW10}.
Recommendations
Cited in
(16)- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Computing large independent sets in a single round
- Input locality and hardness amplification
- A new approach on locally checkable problems
- Distributed strong diameter network decomposition
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Locality in Distributed Graph Algorithms
- On the complexity of local distributed graph problems
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Towards a complexity theory for local distributed computing
- A Local Criterion for Polynomial-Time Stratified Computations
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Making local algorithms wait-free: the case of ring coloring
- Faster deterministic distributed MIS and approximate matching
This page was built for publication: On the locality of some NP-complete problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167029)
