Tutup verteks

Pencarian "minimum vertex cover" dapat ditempuh dengan cara p-aproksimasi, yang memiliki waktu eksekusi polinomial. Untuk permasalahan minimisasi, akan didapatkan solusi ≤ p kali lebih buruk daripada solusi aslinya.
George Karakostas (Mc Master, 2004) telah berhasil memperkecil nilai p yang dimaksud menjadi :G=(E,V)