Set independen pada grafik bebas segitiga kubik

Saya tahu bahwa set independen maksimum pada grafik bebas segitiga kubik adalah NP-lengkap.

Apakah masih NP-complete jika kita memerlukan set independen berukuran persis ? $|V|/2$

Pada dasarnya, contoh instal dari masalah himpunan bebas pada masalah grafik bebas segitiga kubik harus memiliki persis node. Contoh TIDAK memiliki kumpulan ukuran independen kurang dari . $|V|/2$ $|V|/2$

complexity-theory np-complete Mohammad Al-Turkistany
sumber

cs.stackexchange.com/questions/1176/… mungkin relevan.

Louis

Apa contoh NO?

Yuval Filmus

@YuvalFilmus Dia menanyakan masalahnya adalah $\alpha(G) = |G| / 2$ dimana

adalah urutan grafik. Seharusnya dimungkinkan untuk memasukkan beberapa simpul yang terisolasi ke grafik untuk meningkatkan angka independensi. Mohammad, Anda tahu pengurangannya? Apakah tidak mungkin menambahkan simpul terisolasi

untuk mendapatkan reduksi yang diinginkan?

| G |

$|G|$

n / 2 - k

$n/2 - k$

Pål GD

Tidak, saya tidak punya pengurangan.

Mohammad Al-Turkistany

α (G) \geq k

$\alpha(G) \geq k$

α (G) = k

$\alpha(G) = k$

Jawaban:

$|V|/2$ $I$ $v$ $\alpha(v)$ $I$ $\alpha(v) \geq 1$ $v \notin I$ $\sum_v \alpha(v) = 3|I|$ $\alpha(v) \leq 3$ $\alpha(v) \geq 1$ $|I|$ $|I| \leq |V|/2$

$\alpha(v) \in \{0,3\}$ $I$ $I$ $I$ $I$

Yuval Filmus
sumber

YuvalFilmus Terima kasih banyak. Apakah ini memberikan algoritma waktu polinomial untuk masalah saya?

Mohammad Al-Turkistany

Saya kira begitu - apakah Anda setuju?

Yuval Filmus