Penentuan Batas Bawah Minimum Sum Coloring Problem dengan Dekomposisi Graf Bipartit dan Klik

Abstract

Masalah Pewarnaan Jumlah Minimum (Minimum Sum Coloring Problem - MSCP) merupakan varian dari pewarnaan graf yang bertujuan meminimalkan jumlah bobot nilai warna. Mengingat masalah ini memiliki kompleksitas komputasi yang tinggi (NP-Complete), penentuan batas bawah (lower bound) menjadi krusial sebagai tolak ukur evaluasi performa algoritma pewarnaan dalam mencapai solusi optimal. Penelitian ini mengkaji secara teoretis metode penentuan batas bawah MSCP melalui pendekatan ekstraksi graf parsial, yakni dekomposisi bipartit beserta subfamilinya (tree dan path), serta dekomposisi klik. Analisis matematis dan evaluasi komparatif dilakukan dengan mengimplementasikan metode-metode tersebut pada sebuah struktur graf berkepadatan tinggi untuk memvalidasi tingkat keketatan batas bawah yang dihasilkan terhadap nilai chromatic sum aktual. Hasil kajian menunjukkan bahwa rumpun dekomposisi bipartit terbukti valid dalam memformulasi batas bawah, namun memiliki keterbatasan teoretis yang nilainya tidak akan pernah melampaui total verteks ditambah fungsi lantai dari setengah verteksnya. Sebaliknya, dekomposisi klik berhasil mengekstrak kepadatan graf menjadi sekumpulan subgraf lengkap secara lepas tanpa merusak struktur internalnya. Karakteristik ini memungkinkan nilai warna bertumbuh secara kuadratik mengikuti deret aritmetika, sehingga dekomposisi klik disimpulkan lebih unggul dan optimal dalam menghasilkan batas bawah yang jauh lebih ketat dibandingkan rumpun dekomposisi biparti.