Vertex Cover

1. Introduction

Sebuah Tutup Simpul (Vertex Cover / VC) dari sebuah graf terhubung (tak)-berbobot dan tak berarah adalah himpunan bagian dari simpul-simpul V dari G di mana untuk tiap simpul di dalam G, simpul tersebut atau salah satu neighbour nya berada dalam V. Sebuah Tutup Simpul Minimum (Minimum Vertex Cover / MVC, atau Minimum Weighted Vertex Cover / MWVC untuk versi berbobot) dari G adalah VC dengan jumlah simpul terkecil (bila tak berbobot) atau bobot terkecil (bila berbobot) dari seluruh VC yang ada. Sebuah graf dapat memiliki beberapa VC, tetapi nilai dari MVC/MVWC-nya tetap unik.


Ada problem lain bernama Maximum Independent Set (MIS) yang bertujuan untuk mencari himpunan bagian terbesar dari simpul-simpul dalam sebuah graf (tak)-berbobot G di mana tidak ada dua simpul yang berhubungan dalam himpunan bagian tersebut. Yang menarik adalah, komplemen dari MVC pada sebuah graf adalah MIS.

Di akhir tiap visualisasi, ketika algoritma nya memberi highlight dari sebuah solusi MVC pada graf dengan warna oranye. Untuk solusi non-approximation, visualisasi juga akan memberi highlight dari sebuah solusi MIS (yakni V \\ MVC) dengan warna biru muda.

MVC, MWVC, MIS, (and MWIS) semua merupakan masalah optimisasi kombinatorik NP-hard.

1-1. Dua Mode

Ada dua mode yang tersedia: Tak Berbobot (default) dan Berbobot. Anda dapat beralih antara kedua mode tersebut dengan mengklik tab yang sesuai.

Ada algoritma yang bekerja dalam kedua mode dan ada algoritma yang hanya bekerja dalam mode tertentu.

2. Visualisasi

Lihat visualisasi algoritma MVC di sini.


Pada awalnya, tiap simpul dan edge dalam graf masukan diberi warna abu-abu. Seiring berjalannya visualisasi, warna biru akan digunakan untuk menandakan edge yang ter-cover dan warna jingga ketika kita sedang melewati edge itu.

Di akhir algoritma MVC, bila minimum VC ditemukan, simpul-simpul MVC akan diberi warna jingga dan simpul-simpul non-MVC akan diberi warna abu-abu. bila tidak, simpul-simpul yang ditemukan sebagai vertex cover akan diberi warna jingga.

Pada awalnya, tiap simpul dan edge dalam graf masukan diberi warna hitam standar. Seiring berjalannya visualisasi, warna biru muda akan digunakan untuk menandakan edge yang ter-cover dan warna oranye ketika kita sedang melewati edge itu.


Di akhir algoritma MVC, bila minimum VC ditemukan, simpul-simpul MVC akan diberi warna oranye dan simpul-simpul non-MVC (yakni simpul MIS) akan diberi warna biru muda. Bila tidak, jika VC yang ditemukan tidak dibuktikan sebagai solusi minimum (yakni, algoritmanya adalah algoritma approximation), simpul-simpul dari VC tersebut akan diberi warna oranye tanpa mewarnai simpul MIS.

3. Masukan

Terdapat dua metode berbeda untuk membuat graf masukan:

  1. Ubah graf: Anda dapat mengubah graf tak berbobot (berbobot untuk mode MVWC) tak terarah.
  2. Graf contoh: Anda dapat memilih dari graf contoh terhubung tak berbobot (berbobot untuk mode MVWC) tak berarah yang tersedia.

4. Bruteforce

Bruteforce: Mencoba keseluruh 2^V himpunan bagian dari simpul-simpul yang ada. Dalam setiap iterasi, dilakukan pengecekan apakah himpunan bagian saat itu adalah sebuah solusi valid dengan melihat semua E sisi dalam O(E) dan mengecek semua sisi di-cover dengan simpul-simpul dari himpunan tersebut. Algoritma bruteforce ini akan menyimpan ukuran terkecil dari VC yang valid sebagai jawaban.

Algoritma bruteforce ini tersedia dalam versi berbobot dan tak berbobot.

Waktu kompleksitasnya adlaah O(2^V × E), yang sangat lambat. Kita sedang dalam proses meningkatkan visualisasinya agar bagian tidak mendapatkan jawaban lebih bagus 'membosankan' dikeluarkan dan hanya himpunan bagian yang penting yang ditunjukkan.


Diskusi: Terdapat sebuah solusi alternatif O(2^k × E) jika terdapat kasus spesial bahwa k 'tidak-terlalu-besar'.

4-1. Solusi Kasus Spesial

Sayangnya, bagian ini belum didigitalkan/divisualisasikan dan masih dalam proses.

Silakan lihat catatan kuliah CS4234 untuk detailnya.

5. DP pada Pohon

DP pada Pohon: Jika graf berupa pohon, maka problem MVC dapat diselesaikan dengan pemrograman dinamis di mana state yang ada berupa (posisi, ambil_simpul_sekarang). Maka, dapat dilihat bahwa:

DP(u, diambil) = cost[u] + sum(min(DP(v, ambil), DP(v, tidak_diambil))) untuk seluruh anak v dari u, dan
DP(u, tidak_diambil) = sum(DP(v, ambil)) untuk seluruh anak v dari u

Algoritma DP tersebut tersedia dalam versi berbobot dan tak berbobot.

Kompleksitas waktu: O(V), cepat sekali, tapi hanya untuk graf masukan berbentuk pohon.

6. Greedy MVC pada Pohon

DP pada pohon: Sekali lagi, bila graf nya adalah sebuah pohon tak berbobot, kita dapat menyelesaikannya secara greedy dengan melihat bahwa jika ada solusi MVC yang mengambil simpul daun, kita bisa mendapatkan sebuah solusi "bukan terburuk" dengan mengambil parent dari simpul daun tersebut. Setelah menghapus semua simpul yang ter-cover, kita dapat mengulangi langkah ini hingga semua simpul ter-cover.

Algoritma greedy tersebut hanya tersedia dalam versi tak berbobot.

Kompleksitas waktu: O(V), cepat sekali, tapi hanya untuk graf masukan berbentuk pohon tak berbobot.

7. Teorema Kőnig

Teorema Kőnig: Menurut teorema Kőnig, ukuran MVC dalam graf bipartit tak berbobot sama dengan jumlah pencocokan maksimum dalam graf bipartit. Dalam kasus graf bipartit berbobot, kita dapat melihat bahwa teorema ini juga berlaku, dengan sedikit perubahan di cara kita membuat grafnya. Dalam visualisasi ini, kita mereduksi problem aliran maksimum untuk mendapatkan nilai MVC.

Algoritma ini tersedia dalam versi berbobot dan tak berbobot.

Kompleksitas waktu: O(V × E) (tak berbobot; bisa lebih kecil dengan preprocessing), O(E^2 V) atau O(E^2 × V)/O(V^2 × E) (berbobot, bergantung pada algoritma aliran maksimum yang digunakan).

8. Algoritma-algoritma Penaksiran

Terdapat dua algoritma approximation untuk MVC:
  1. Untuk versi tak berbobot, kita mempunyai algoritma deterministik 2-approximation, atau probabilistik 2-approximation (dalam ekspektasi),
  2. Untuk versi berbobot, kita mempunyai algoritma Bar-Yehuda dan Even 2-approximation.
Perlu dicatat bahwa algoritma-algoritma ini hanya akan menghasilkan MVC "dengan penaksiran", di mana nilai tersebut bukanlah nilai minimum sebenarnya, namun sudah cukup kecil.

8-1. Bukti Rasio Approximation

Sayangnya, bagian ini belum didigitalkan/divisualisasikan dan masih dalam proses.

Silakan lihat catatan kuliah CS4234 untuk detailnya.