Menemukan subgraf bebas 3-klik terbesar yang diinduksi

Pertimbangkan masalah ini:

Diberikan grafik tidak terarah $G = (V, E)$ , Temukan $G' = (V', E')$ seperti yang:

$G'$ adalah subgraph yang diinduksi dari $G$

$G'$ tidak memiliki 3-klik

$|V'|$ maksimal

Jadi jumlah simpul paling sedikit harus dihilangkan $G$ sehingga 3-klik dihilangkan.

Masalah yang setara adalah menemukan 2-pewarnaan untuk $G$ sedemikian rupa sehingga jika $(v_1, v_2, v_3) \in V$ dan $((v_1, v_2), (v_2, v_3), (v_3, v_1)) \in V$ ,

$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$
Perbedaan (absolut) antara jumlah node dengan warna 1 dan jumlah node dengan warna 2 adalah maksimal.

Adakah yang bisa memikirkan algoritma waktu polinomial untuk menyelesaikan salah satu masalah ini?

algorithms graph-theory graphs optimization Alexandre
sumber

Apakah Anda tahu bahwa ada adalah algoritma waktu polinomial, atau Anda hanya berharap untuk satu?

Luke Mathieson

Saya baru sadar, dua definisi masalah Anda tidak cocok! Yang kedua memaksakan kondisi yang disebabkan oleh subgraph

V - V^{'}

$V-V'$ juga bebas segitiga. Saya tahu bahwa ini NP-Complete untuk menentukan apakah partisi tersebut ada: cstheory.stackexchange.com/questions/65/h-free-cut-problem . Sedangkan deskripsi awal memungkinkan grafik yang diinduksi dari

V - V^{'}

$V-V'$ mengandung segitiga. Yang mana yang benar?

Aryabhata

@LukeMathieson: Saya percaya kelas o grafik memiliki solusi polinomial-waktu karena saya mencapai masalah di atas dari masalah berikut yang memiliki solusi polinomial-waktu: "Diberikan satu set interval bilangan bulat N, pilih sebanyak mungkin sehingga tidak ada 3 intersect . "

Alexandre

@Alexandre: Grafik interval spesial. Masalah NP-Hard yang terkenal ada di P, ketika terbatas pada grafik interval.

Aryabhata

@Aryabhata: Subgraf yang diinduksi adalah G ', dan tidak dapat memiliki 3-klik. Oleh karena itu, tidak dapat memiliki segitiga, persis sama dengan deskripsi kedua.

Alexandre

Menemukan subgraf bebas 3-klik terbesar yang diinduksi

Jawaban: