Pewarnaan (Δ+1) dan Himpunan Independen Maksimal Paralel Deterministik yang Benar-benar Efisien Kerja

Masalah menghitung pewarnaan (Δ+1) dan himpunan independen maksimal (MIS) secara paralel telah menjadi topik sentral dalam ilmu komputer teoretis selama beberapa dekade. Untuk graf $G=(V,E)$ dengan $n=|V|$ simpul dan $m=|E|$ sisi, pewarnaan (Δ+1) memberikan warna dari $\{1,\dots ,\Delta +1\}$ ke simpul sedemikian rupa sehingga tidak ada dua simpul bertetangga yang berbagi warna yang sama, dengan $\Delta$ adalah derajat maksimum. Himpunan independen maksimal adalah himpunan simpul yang tidak ada dua di antaranya bertetangga, dan tidak ada simpul lain yang dapat ditambahkan tanpa melanggar independensi. Kedua masalah ini adalah primitif fundamental dalam komputasi terdistribusi dan paralel, dengan aplikasi dalam penjadwalan, alokasi sumber daya, dan koordinasi jaringan.

Penelitian sebelumnya telah menetapkan algoritma paralel teracak yang mencapai kerja $O(n+m)$ dan kedalaman $O(\mathrm{poly}\log n)$, tetapi algoritma deterministik dengan jaminan yang sama masih sulit diwujudkan. Tantangan utamanya adalah pemecahan simetri deterministik biasanya memerlukan lebih banyak kerja atau kedalaman yang lebih besar. Hutton dan Melrod mengatasi kesenjangan ini dengan menyediakan algori

Hasil utama makalah ini dinyatakan sebagai berikut: Terdapat algoritma paralel deterministik yang menghitung pewarnaan $(\Delta +1)$ dan himpunan independen maksimal untuk graf sederhana dengan $n$ simpul dan $m$ sisi dalam kerja $O(n+m)$ dan kedalaman $O(\mathrm{poly}\log n)$. Secara spesifik, kedalamannya adalah $O({\log }^{2}n)$ untuk kedua masalah. Ini menyamai kerja algoritma teracak terbaik dan meningkatkan algoritma deterministik sebelumnya yang memerlukan kerja $O(m\log n)$ atau kedalaman $O({\log }^{3}n)$.

Penulis memberikan analisis rinci tentang kerja dan kedalaman. Mereka menunjukkan bahwa total jumlah operasi dibatasi oleh $c(n+m)$ untuk suatu konstanta $c$, dan kedalaman dibatasi oleh $c^{\prime }{\log }^{2}n$ untuk suatu konstanta $c^{\prime }$. Algoritma bersifat deterministik, artinya tidak bergantung pada keacakan apa pun, yang krusial untuk aplikasi yang memerlukan reproduktibilitas dan jaminan kasus terburuk. Hasil ini berlaku untuk model EREW PRAM, model standar untuk komputasi paralel. Makalah ini juga membahas perluasan ke CRCW PRAM dan ke pengaturan terdistribusi, di mana algoritma dapat diimplementasikan dalam model CONGEST dengan putaran $O(\log n)$ untuk MIS dan putaran $O({\log }^{2}n)$