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 penjumlahan 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 subkelasnya (pohon dan lintasan), serta dekomposisi klik. Analisis matematis dan evaluasi komparatif dilakukan dengan mengimplementasikan metode-metode tersebut pada sebuah contoh struktur graf untuk memvalidasi tingkat keketatan batas bawah yang dihasilkan terhadap nilai chromatic sum aktual. Hasil kajian menunjukkan bahwa dekomposisi bipartit terbukti valid dalam memformulasi batas bawah, namun memiliki keterbatasan teoretis yang nilainya tidak akan pernah melampaui total simpul ditambah fungsi lantai dari setengah simpulnya. Sebaliknya, dekomposisi klik berhasil mengekstrak kepadatan graf menjadi sekumpulan subgraf lengkap secara lepas. Karakteristik ini memungkinkan nilai warna bertumbuh secara kuadratik mengikuti deret aritmetika, sehingga dekomposisi klik dalam contoh tersebut lebih unggul dalam menghasilkan batas bawah dibandingkan rumpun dekomposisi bipartit.