Pemecahan Simetri Terdistribusi pada Graf Acak Hiperbolik

MIS dan Pencocokan Maksimal lebih sulit daripada pewarnaan Δ+1 pada HRG, tetapi algoritma yang ketat secara polinomial tetap ada

Yannic Maus; Janosch Ruff; Sonia Simons; George Skretas· 2026· DOI 10.48550/arXiv.2607.09170

Masalah inti

Jaringan dunia nyata seperti internet menunjukkan distribusi derajat hukum pangkat dan koefisien pengelompokan yang tinggi. Graf acak hiperbolik (HRG) adalah model generatif yang menangkap sifat-sifat ini, menyediakan kerangka teoretis untuk mempelajari algoritma pada jaringan realistis. Didorong oleh pengamatan bahwa beberapa algoritma berkinerja lebih baik pada jaringan dunia nyata daripada yang disarankan oleh jaminan kasus terburuknya, penulis merancang dan menganalisis algoritma terdistribusi dengan asumsi bahwa graf masukan adalah HRG. Penelitian sebelumnya telah menunjukkan bahwa masalah pemecahan simetri klasik dari (Δ + 1) -pewarnaan, di mana Δ adalah derajat maksimum, dapat diselesaikan dalam 2 putaran pada HRG [Maus dan Ruff; SODA'26]. Sebaliknya, makalah ini membuktikan bahwa masalah pemecahan simetri terkait dari himpunan bebas maksimal (MIS) dan pencocokan maksimal (MM) jauh lebih sulit pada HRG.

Hasil utamanya ada dua: (1) batas bawah Ω (\frac{lo g lo g n}{lo g lo g lo g n}) untuk MIS dan MM pada HRG, dan (2) batas atas \tilde{O} (lo g^{5/3} lo g n) putaran untuk kedua masalah. Batas-batas ini ketat secara polinomial, artinya batas atas dan bawah cocok hingga faktor polilogaritmik. Batas bawah ditetapkan dengan menyematkan pohon d -ary ke dalam HRG dan menerapkan teknik batas bawah terdistribusi yang diketahui. Algoritma batas atas dirancang khusus untuk memanfaatkan struktur HRG, mencapai waktu jalan yang jauh lebih cepat daripada yang mungkin pada graf umum. Ini menunjukkan bahwa meskipun MIS dan MM lebih sulit daripada (Δ + 1) -pewarnaan pada HRG, keduanya masih lebih mudah daripada pada graf sembarang.

Jaringan dunia nyata seperti internet menunjukkan distribusi derajat hukum pangkat dan koefisien pengelompokan yang tinggi. Graf acak hiperbolik (HRG) adalah model generatif yang menangkap sifat-sifat ini, menyediakan kerangka teoretis untuk mempelajari algoritma pada jaringan realistis. Didorong oleh pengamatan bahwa beberapa algoritma berkinerja lebih baik pada jaringan dunia nyata daripada yang disarankan oleh jaminan kasus terburuknya, penulis merancang dan menganalisis algoritma terdistribusi dengan asumsi bahwa graf masukan adalah HRG. Penelitian sebelumnya telah menunjukkan bahwa masalah pemecahan simetri klasik dari (Δ + 1) -pewarnaan, di mana Δ adalah derajat maksimum, dapat diselesaikan dalam 2 putaran pada HRG [Maus dan Ruff; SODA'26]. Sebaliknya, makalah ini membuktikan bahwa masalah pemecahan simetri terkait dari himpunan bebas maksimal (MIS) dan pencocokan maksimal (MM) jauh lebih sulit pada HRG.

Penulis menetapkan batas bawah untuk MIS dan MM pada HRG dengan memanfaatkan wawasan struktural baru. Mereka menunjukkan bahwa HRG mengandung pohon d -ary dengan tinggi dan derajat yang besar, yang memungkinkan mereka mengadaptasi dan mengangkat hasil ketidakmungkinan sebelumnya untuk algoritma terdistribusi ke pengaturan HRG. Secara spesifik, mereka membuktikan batas bawah Ω (\frac{lo g lo g n}{lo g lo g lo g n}) putaran untuk MIS dan MM dalam model LOCAL. Untuk melengkapi batas bawah ini, mereka merancang algoritma yang disesuaikan untuk HRG yang menyelesaikan MIS dan MM dalam \tilde{O} (lo g^{5/3} lo g n) putaran dengan probabilitas tinggi. Ini meningkatkan batas bawah kasus terburuk umum dari Ω (min {lo g Δ, lo g n}) putaran [Khoury dan Schild; FOCS'25]. Algoritma tersebut memanfaatkan geometri hiperbolik yang mendasari untuk mencapai pemecahan simetri yang lebih cepat.

Makalah ini memberikan pemahaman yang bernuansa tentang pemecahan simetri pada HRG. Kontras yang mencolok antara algoritma 2 putaran untuk (Δ + 1) -pewarnaan dan batas bawah Ω (\frac{lo g lo g n}{lo g lo g lo g n}) untuk MIS dan MM menyoroti bahwa tidak semua masalah pemecahan simetri sama mudahnya pada HRG. Wawasan struktural bahwa HRG mengandung pohon d -ary besar adalah kontribusi kunci, karena memungkinkan adaptasi hasil ketidakmungkinan dari graf umum ke pengaturan HRG. Algoritma yang ketat secara polinomial menunjukkan bahwa batas bawah pada dasarnya optimal. Karya ini membuka arah baru untuk mempelajari masalah terdistribusi lainnya pada HRG dan untuk memahami dampak model jaringan pada desain algoritma. Hasilnya juga menunjukkan bahwa jaringan dunia nyata, yang sering menyerupai HRG, mungkin memerlukan strategi algoritmik yang berbeda untuk tugas pemecahan simetri yang berbeda.

Praktisi dan peneliti ilmu komputer

Membuka konten member…