Vi presenterar en deterministisk distribuerad algoritm som beräknar en (2Δ − 1)-kant-färgning, eller till och med list-kantfärgning, i någon n-node graf med maximal grad Δ, i O(log 8 Δ·log n) rundor. Detta besvarar en av de långvariga öppna frågorna av distribuerade grafalgoritmer från slutet av 1980-talet, som bad om en polylogaritmisk-tid algoritm. Se t.ex. Open Problem 4 i Barenboims och Elkins bok Distributed Graph Coloring. De tidigare bästa runda komplexen var 2 O( ε log n) av Panconesi och Srinivasan [STOC'92] och O( Δ) + O(log * n) av Fraigniaud, Heinrich och Kosowski [ FOCS'16]. En följd av vår deterministiska list-kant-färgning förbättrar också den randomiserade komplexiteten av (2Δ − 1)-kantfärgning till poly(log log n) rundor. Den viktigaste tekniska ingrediensen är en deterministisk distribuerad algoritm för hypergraph maximal matchning, som vi tror kommer att vara av intresse utöver detta resultat. I varje hypergraf av rank r -där varje hyperedge har som mest r hörn -med n noder och maximal grad Δ, beräknar denna algoritm en maximal matchning i O(r 5 log 6+log r Δ · log n) rundor. Denna hypergraph matchande algoritm och dess förlängningar leder också till ett antal andra resultat. Framför allt får vi en polylogaritmisk tidsdeterministisk distribuerad maximal oberoende uppsättning (MIS) algoritm för grafer med avgränsade kvartersoberoende, vilket svarar Open Problem 5 i Barenboim och Elkins bok, en (log Δ/ε) O(log 1/ε)round deterministisk algoritm för (1 + ε)-tillnärmning av maximal matchning, och en kvasi-polylogaritmisk tid deterministisk distribuerad algoritm för orientering λ-arbolicity grafer med ut-grader som mest (1 + ε)λ, för alla konstant ε > 0, vilket delvis svarar Open Problem 10 Barenboim och Elkin bok. ε log n), på grund av Panconesi och srinivasan [PS92]. Panconesi och Rizzi påpekade år 2001 [PR01] att "även om maximal matchning kan beräknas i polylogaritmisk tid, i n, i den distribuerade modellen [HKP98], är det ett decennium gammalt öppet problem om samma körtid är möjligt för de återstående 3 strukturer." Statusen är densamma som i dag, efter nästan två årtionden till. I synnerhet för kantfärgning som är vårt främsta mål, Barenboim och Elkin uppgav följande problem i sin senaste Distributed 1 Om det senare inte är fallet, det räcker att prova exponentiellt ökande uppskattningar. 2 I LOCAL modellen kan meddelanden vara av godtycklig storlek. En variant av modellen där meddelandena måste vara av avgränsad storlek kallas CONGEST-modellen [Pel00]. Våra edge-färga algoritmer och våra MIS och vertex-färga algoritmer för grafer av avgränsade område oberoende i själva verket arbeta med små O(log n)-bit-size meddelanden. För läsbarhetens skull undviker vi att uttryckligen diskutera detaljerna i denna aspekt.
Fischer m.fl. REF gav en randomiserad (2- 1)-kantig färgalgoritm med komplexitet O(log 8 log n).
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}