Peneliti Kopenhagen dan DTU kembangkan algoritma pewarnaan peta empat warna yang jauh lebih cepat
Tim peneliti dari Universitas Kopenhagen, DTU, dan mitra internasional memaparkan algoritma pewarnaan empat warna untuk peta yang berjalan dalam waktu linear. Hasil linear itu masih berstatus pracetak di arXiv.
Dua profesor dari Universitas Kopenhagen dan DTU Compute, bersama kolega dari beberapa negara, memaparkan algoritma untuk mewarnai peta dengan empat warna yang efisien, sebagaimana diberitakan pada 17 dan 18 November 2026. Menurut rilis yang dimuat jaringan ECMI, ini algoritma paling efisien sampai saat ini untuk tugas tersebut, dan timnya mengerjakannya selama sekitar satu dekade.
Latar: pertanyaan sejak 1852
Pertanyaannya sederhana: bisakah setiap peta diwarnai dengan empat warna sehingga dua wilayah yang bersebelahan tidak pernah berwarna sama? Pertanyaan itu muncul pada 1852. Menurut TechSavvy Media, ia diajukan oleh matematikawan Inggris Francis Guthrie, yang mendapati bahwa peta wilayah administrasi Inggris cukup memakai empat warna. Jawaban "ya" baru terbit lewat bukti pada 1976, yang kala itu diperdebatkan karena bergantung pada perhitungan komputer yang sulit diperiksa matematikawan lain. Bukti yang lebih mudah dipahami hadir pada 1997. Bukti tersebut juga mampu menghasilkan pewarnaan empat warna, tetapi lambat ketika diterapkan pada peta besar.
Apa yang baru
Dalam bahasa matematika, peta disebut graf planar. Peneliti menemukan bahwa graf semacam itu memuat jauh lebih banyak reducible configuration daripada yang diperkirakan sebelumnya. Istilah ini merujuk pada bagian kecil graf yang menjadi titik awal untuk menentukan pewarnaan. Carsten Thomassen dari DTU menggambarkannya sebagai pegangan untuk memulai pewarnaan, dan menurutnya jumlah pegangan di dalam graf ternyata sangat besar, hal yang sebelumnya tidak diketahui.
Karena titik awal dapat dicari di banyak tempat, proses pewarnaan bisa dimulai dari berbagai lokasi, sehingga peta yang sangat besar pun dapat diwarnai jauh lebih cepat. Mikkel Thorup dari Universitas Kopenhagen menyatakan bahwa bukti-bukti terdahulu menunjukkan pewarnaan empat warna selalu mungkin, tetapi kurang mampu menentukan warna tiap wilayah secara nyata. Algoritma baru ini, katanya, menawarkan cara yang jauh lebih cepat.
Dari kuadratik ke linear
Thomassen menjelaskan bahwa laju komputasi berpindah dari waktu kuadratik ke waktu linear. Artinya, bila jumlah wilayah pada peta menjadi 10 kali lebih banyak, waktu komputasi hanya sekitar 10 kali lebih lama. Dengan algoritma lama, waktunya akan sekitar 100 kali lebih lama.
Makalah pertama tentang riset ini dipresentasikan di FOCS'26, konferensi terkemuka di bidang ilmu komputer teoretis, dan meraih Best Paper Award. Menurut halaman arXiv makalah lanjutan, algoritma pada makalah FOCS tersebut berjalan dalam waktu O(n log n), yang disebut hampir linear.
Makalah lanjutan: O(n)
Tak lama setelah makalah FOCS terbit, tim merilis makalah lanjutan berjudul "Four-Coloring Planar Graphs in Linear Time", yang diajukan ke arXiv pada 30 Oktober 2026. Dalam abstraknya, para penulis menyatakan bahwa pewarnaan empat warna pada graf planar dapat dilakukan dalam waktu O(n), yang mereka sebut optimal.
Hambatan pada algoritma sebelumnya adalah kebutuhan akan O(log n) perubahan Kempe untuk memperluas pewarnaan rekursif ke konfigurasi yang dapat direduksi. Menurut abstrak itu, setiap perubahan Kempe dapat melibatkan sebagian tetap dari graf dan memakan waktu linear. Makalah lanjutan menunjukkan bahwa seluruh perubahan tersebut dapat diidentifikasi dan dijalankan dalam waktu O(n) total, lewat praproses graf. Para penulis juga mencatat bahwa tantangan di sini lebih menyangkut struktur data, berbeda dari makalah sebelumnya yang bertumpu pada pemahaman teori graf yang baru.
Siapa saja penelitinya
Selain Thorup dan Thomassen, penelitinya meliputi Ken-ichi Kawarabayashi dari National Institute of Informatics di Tokyo, Bojan Mohar dari Simon Fraser University, serta Yuta Inoue dan Atsuyuki Miyashita dari Universitas Tokyo. Sesuai tradisi matematika, semua penulis dianggap berkontribusi setara.
Apa artinya bagi pembaca
Bagi mahasiswa dan praktisi teknik, hasil ini menarik karena selisih antara waktu kuadratik dan linear menentukan apakah suatu masalah masih praktis pada data besar. Namun perlu dicatat bahwa hasil O(n) berstatus pracetak, dan halaman arXiv yang dibuka tidak menyebut adanya tinjauan sejawat. Hasil yang sudah dipresentasikan secara resmi adalah makalah FOCS'26 dengan waktu O(n log n). Rilis Universitas Kopenhagen juga menyebut bahwa pemahaman baru tentang struktur graf ini membuka kemungkinan untuk mempelajari permukaan berlubang, seperti ban renang atau keju Emmental.