NP menyelesaikan masalah grafik tentang properti struktural

(Pertanyaan ini sedikit "survei".)

Saya saat ini sedang mengerjakan masalah di mana saya mencoba untuk membagi tepi turnamen menjadi dua set, yang keduanya diperlukan untuk memenuhi beberapa sifat struktural. Masalahnya "terasa" cukup sulit, dan saya sepenuhnya berharap itu menjadi -complete. Untuk beberapa alasan saya mengalami kesulitan bahkan menemukan masalah serupa dalam literatur. $\mathcal{NP}$

Contoh masalah yang saya anggap sebanding dengan yang saya hadapi:

Mengingat turnamen berbobot , apakah ada busur umpan balik yang ditetapkan di yang ujungnya memenuhi ketidaksetaraan segitiga? $G = (V,E,w)$ $G$

Perhatikan perbedaan pada masalah set busur umpan balik tradisional: Saya tidak peduli tentang ukuran set, tetapi saya peduli apakah set itu sendiri memiliki properti struktural tertentu.

Sudahkah Anda menemui masalah keputusan yang terasa serupa dengan ini? Apakah Anda ingat apakah mereka -Lengkap atau ? Semua bantuan apapun diapresiasi. $\mathcal{NP}$ $\mathcal{P}$

cc.complexity-theory reference-request np-hardness G. Bach
sumber

Mungkin Anda bisa menjelaskan sifat struktural masalah Anda, ada banyak ahli di sini yang akrab dengan bukti NPC dan alih-alih referensi Anda bisa mendapatkan bukti NPC :-)

Marzio De Biasi

@MarzioDeBiasi Saya sangat ingin menghindari diberikan bukti untuk masalah yang saya hadapi; ini adalah pertama kalinya saya melakukan penelitian aktual dan saya ingin melihat di mana saya bisa mendapatkan sendiri :)

G. Bach

Bagi saya, pertanyaannya terdengar terlalu samar, dan sulit untuk menebak apa yang sebenarnya ditanyakan. Mungkin, pertanyaan harus dibuat lebih spesifik: apa yang Anda maksud dengan "merasa mirip dengan ini" dan apa yang Anda maksud dengan "busur umpan balik yang diatur dalam G yang ujung-ujungnya memenuhi ketidaksetaraan segitiga"; Anda ingin referensi tentang masalah set busur umpan balik, atau pada masalah lain?

Yoshio Okamoto

@YoshioOkamoto Saya menyadari bahwa ada beberapa ambiguitas dalam pertanyaan, dan saya berharap contohnya akan menjelaskan sebagian. Dengan "busur umpan balik diatur dalam G tepi yang memenuhi ketidaksamaan segitiga" Maksudku: jika

adalah rangkaian umpan balik dan

, lalu

F

$F$

(a, b)

$(a,b)$

(b, c)

$(b,c)$

(a, c)

$(a,c)$

\in F

$\in F$

w (a, b) + w (b, c) \geq w (a, c)

$w(a,b) + w(b,c) \ge w(a,c)$ harus menahan

untuk memenuhi properti itu. Sebelumnya saya hanya pernah menemui masalah sejenis

, tapi saya ingin

memiliki properti yang tidak terkait dengan kardinalitasnya.

F

$F$

| F | \leq k

$|F| \le k$

F

$F$

G. Bach

dapatkah seseorang memberikan tautan / ref ke "masalah set busur umpan balik tradisional" ...?

vzn

Jawaban:

Saya pikir ada banyak masalah serupa. Berikut adalah dua versi vertex dan satu versi edge:

1) Apakah grafik yang diberikan memiliki set simpul umpan balik independen ? (kami tidak peduli tentang ukuran set). Masalah ini sudah selesai NP; buktinya dapat diperoleh dari bukti Teorema 2.1 di Garey, Johnson & Stockmeyer .

2) Apakah grafik yang diberikan memiliki penutup simpul yang menginduksi pohon ? (kami tidak peduli tentang ukuran set). Makalah ini memberikan bukti kelengkapan NP untuk masalah ini (Teorema 2); bahkan untuk grafik bipartit.

3) Apakah grafik yang diberikan memiliki tepi yang mendominasi mengatur tepi yang membentuk subgraph reguler yang diinduksi $1$ ? (juga dikenal sebagai dominasi induced matching atau efisien edge mendominasi; versi vertex diberikan dalam jawaban kedua oleh Mohammad. Sekali lagi, kami tidak peduli tentang ukuran set). Masalah ini NP-lengkap (terkenal, pertama kali terbukti di sini ), bahkan untuk grafik bipartit planar.

Dua masalah pertama adalah contoh khusus dari kelas masalah yang disebut stable- : Misalkan menjadi properti grafik. Apakah grafik yang diberikan memiliki simpul penutup memuaskan ? Lebih banyak kasus NP-lengkap serta kasus-kasus yang dapat dipecahkan secara polinomi dapat ditemukan dalam makalah ini dan dalam makalah ini (dan referensi diberikan di sana). $\pi$ $\pi$ $\pi$

vb le
sumber

Persis seperti itulah masalah yang saya cari!

G. Bach

@ G.Bach Karena ini menjawab pertanyaan Anda, saya sarankan Anda menerima jawabannya dan memberikan hadiahnya.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany Saya setuju; untuk beberapa alasan, saya hanya akan bisa memberi hadiah dalam satu jam.

G. Bach

Terima kasih atas kiriman bagus Anda. Saya berpikir untuk beberapa lama untuk garis yang sama.

Mohammad Al-Turkistany

$C$ $C$ $NP$ $NP$

DW Bange, AE Barkauskas, dan PJ Slater. Set dominasi yang efisien dalam grafik . Aplikasi matematika diskrit, Proc. 3rd SIAM Conf., Clemson / South Carolina 1986, 189-199 (1988)., 1988.

Mohammad Al-Turkistany
sumber

Varian lain dari Dominating Set adalah Connected Dominating Set dan Independent Dominating Set .

Radu Curticapean

@RaduCurticapean Tetapi dengan varian ini Anda peduli tentang ukuran solusinya.

vb le

Ya, saya mengabaikan ini.

Radu Curticapean

$NP$ $NP$

Sebuah lubang adalah siklus chordless dengan panjang lebih dari tiga. Siklus dalam grafik berarah tidak memiliki chord jika panjangnya lebih besar dari 3 dan tidak ada dua simpulnya yang bergabung dengan tepi grafik berarah yang tidak termasuk dalam siklus.

$NP$ $P$

$NP$

Pentingnya mendeteksi struktur lubang ganjil dalam grafik disorot oleh terobosan terbaru dari Theor Perfect Graph Theorem . Ini menunjukkan bahwa grafik sempurna jika dan hanya jika baik grafik komplementernya memiliki lubang ganjil.

Mohammad Al-Turkistany
sumber

Sebuah siklus diinduksi siklus jika dan hanya jika itu adalah siklus chordless (juga disebut hole).

Mohammad Al-Turkistany

Kedua jawaban Anda terdengar seperti masalah yang saya cari, terima kasih!

G. Bach