Apa kerumitan masalah grafik ini?

Diberi graf sederhana yang tidak terarah , temukan subset dari simpul, sedemikian rupa sehingga $G$ $A\neq \emptyset$

untuk setiap titik setidaknya setengah dari tetangga juga dalam , dan $x\in A$ $x$ $A$
ukuran adalah minimum. $A$

Yaitu, kami sedang mencari sebuah cluster, di mana setidaknya setengah dari lingkungan setiap vertex internal tetap internal. Keberadaan kluster semacam itu sudah jelas, karena seluruh himpunan simpul selalu memiliki properti 1. Tetapi seberapa sulitkah untuk menemukan kluster terkecil (yang tidak kosong)? $V(G)$

Apakah ada nama standar untuk masalah ini? Apa yang diketahui tentang kerumitannya?

graph-theory graph-algorithms np-hardness Andras Farago
sumber

Tampaknya merupakan varian dari masalah Pemisahan yang Memuaskan . Saya tidak tahu apakah varian Anda diketahui dan telah terbukti sebagai NPC; tetapi mungkin pengurangan dari k-klik harus berfungsi: tautkan setiap node

dari grafik asli ke

node dari

"klik eksternal" ukuran

(setiap node memiliki klik eksternal). Kemudian Anda dapat menemukan himpunan nontrivial

dengan ukuran

jika dan hanya jika

v_{i}

$v_i$

k + 1

$k+1$

C_{i}

$C_i$

2 (k + 1)

$2(k+1)$

A

$A$

k

$k$

k

$k$ -clique ada di grafik asli (Anda harus memilih setidaknya satu simpul, tetapi Anda harus menghindari klik eksternal). Tapi itu hanya ide; jika saya punya cukup waktu saya akan mencoba melihat apakah pengurangannya sudah benar.

Marzio De Biasi

@MarzioDeBiasi Terima kasih, setelah beberapa pencarian saya menemukan bahwa Masalah Partisi Memuaskan memang terkait. Namun, di setiap varian yang bisa saya temukan, mereka mencari partisi, bukan untuk satu set. Tidak jelas, bagaimana mereka terkait. Dalam pengurangan Anda, kecuali jika saya salah mengerti sesuatu,

-clique dari grafik asli tidak memenuhi definisi, karena setiap node di dalamnya akan memiliki

tetangga internal, tetapi setidaknya

tetangga eksternal, karena penambahan eksternal klik-klik.

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Andras Farago

Saya pikir masalah ini dikenal sebagai "aliansi defensif"

daniello

@daniello: hebat, saya mencari di survei IG Yero, JA Rodriguez-Velazquez, "aliansi defensif dalam grafik: survei", 2013 tetapi tidak menemukan kata "setengah"; ketika saya punya cukup waktu saya akan membacanya dengan cermat; kemungkinan masalah OP sudah diketahui!

Marzio De Biasi

Tampaknya dirumuskan sebagai "setiap simpul memiliki setidaknya tetangga di dalam sebanyak di luar" yang sama seperti dalam pertanyaan hingga pembulatan, dan mungkin termasuk / tidak termasuk simpul itu sendiri dalam hitungan

daniello

Jawaban:

Ini adalah pengurangan dari Klik untuk masalah Anda.

Kita mulai dengan sebuah contoh dari Clique: grafik dan sebuah integer , biarkan . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Klik tetap menjadi NPC bahkan di bawah batasan bahwa (sketsa bukti: jika kemudian tambahkan mana $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ dalam grafik baru). dan hubungkan ke semua node dan minta klik ukuran $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Jadi kita mengasumsikan bahwa dalam , . Untuk setiap simpul yang kita buat klik "eksternal" dari ukuran (setiap simpul $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ clique memiliki setidaknya $C_i$ tetangga). $2(k+1)$

Jika adalah derajat dari , kita menghubungkan ke node . $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$

Dalam dihasilkan , setiap memiliki derajat ; jadi karena setidaknya satu simpul harus dipilih. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Jelas bahwa jika salah satu dari simpul termasuk dalam maka setidaknya node juga harus dimasukkan di dalamnya. Perhatikan bahwa jika node asli memiliki maka setidaknya satu simpul dari terkait harus disertakan, yang mengarah ke . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Jadi kita bisa membangun satu set dari ukuran minimum jika dan hanya jika $A$ $|A| = k$ $G$ berisi klik ukuran . $k$

Contoh pengurangan di mana kita bertanya apakah grafik diwakili oleh simpul kuning dan tepi tebal berisi klik ukuran (a segitiga). $G$ $k = 3$

Node biru (dikelompokkan untuk keterbacaan yang lebih baik) adalah , tepi merah adalah hubungan antara node dengan . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
sumber

@ WillardZhan: karena setiap simpul

memiliki derajat

oleh konstruksi, jadi jika

mengandung satu simpul, itu harus mengandung setidaknya

tetangga (dan sama berlaku untuk semua simpul

), jadi

. "Ukuran minimum"

dapat dicapai hanya jika

adalah klik ukuran

G^{'}

$G'$

\geq 2 (k - 1)

$\geq 2(k-1)$

A

$A$

2 (k - 1) / 2 = k - 1

$2(k-1)/2 = k-1$

A

$A$

| A | \geq k

$|A| \geq k$

k

$k$

A

$A$

k

$k$

Marzio De Biasi

@ WillardZhan: Saya menambahkan kondisi lain ke masalah klik awal (tetapi harus tetap NPC) ... Saya masih memeriksanya (tidak secara keseluruhan yakin itu benar).

Marzio De Biasi

k^{'}

$k'$

t

$t$

@ WillardZhan: Saya pikir itu benar, karena dalam paragraf itu saya merujuk pada pengurangan dari Clique [contoh

(G, k)

$(G,k)$ ] untuk klik Clique +

m a x (d e g (v_{i})) \leq 2 (k - 1)

$max(deg(v_i)) \leq 2(k-1)$ [contoh

(G^{'}, k^{'})

$(G',k')$ ]

t

$t$ adalah jumlah dari node (klik) untuk ditambahkan ke G untuk mendapatkan contoh baru dari Clique yang menambah kendala.

Marzio De Biasi