Masalah NP-hard pada cographs

12

Pertanyaan ini mirip dengan masalah NP-hard pada pohon :

Ada sejumlah besar masalah NP-lengkap yang dapat ditelusuri pada cographs . Apakah ada masalah yang diketahui yang tetap melengkapi NP ketika dibatasi untuk cographs?

Untuk lebih tepatnya saya tertarik pada contoh-contoh di mana input semata-mata terdiri dari tanda kutip, tidak tertimbang .

Dua komentar:

Untuk cographs tertimbang masalah seperti itu disebutkan di sini - TSP dengan dua pelancong
Gambar adalah "kelas dasar" lebar klik seperti pohon adalah kelas dasar untuk lebar pohon.

MEMPERBARUI

Beberapa pemikiran lebih lanjut (saya tidak begitu yakin tentang): Jika input benar-benar hanya sebuah cograph, pertanyaannya harus dari jenis "Apakah cograph memiliki properti X?". Akan cukup jika ada masalah seperti itu untuk pohon, sejak itu pertanyaannya adalah "Apakah cotree dari cograph memiliki properti X?".

cc.complexity-theory np-hardness graph-algorithms Martin Lackner
sumber

Jadi, agar tidak menjadi duplikat (tidak jadi) pertanyaan, mungkin kita juga memerlukan masalah NP-complete ini agar waktu polinomial terpecahkan di pohon?

Hsien-Chih Chang 張顯之

Akan menyenangkan tentunya. Namun saya akan ditentang bahkan jika ini tidak terjadi. Terutama karena semua contoh yang diberikan di utas asli tidak menjawab pertanyaan saya (untuk pemahaman saya).

Martin Lackner

11

Mungkin masalah terbuka favorit saya adalah menarik: masalah clique-cover edge pada cographs. Dalam masalah clique-cover edge, Anda ingin menutupi tepi cograph dengan jumlah klik minimum. Tidak diketahui apakah masalah ini NP-complete.

$K_n^m$ $m$ $n$ $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Ton Kloks
sumber

10

Beberapa masalah tetap NP-lengkap ketika dibatasi untuk cographs. Daftar pewarnaan, angka achromatic, dan isomorfisma subgraph yang diinduksi tetap NP-lengkap.

[1] Hans L. Bodlaender. Angka Achromatic adalah NP-lengkap untuk grafik dan interval interval. Inf. Proses. Lett., 31 (3): 135–138, 1989

[2] Klaus Jansen dan Petra Scheffler. Pewarnaan umum untuk grafik seperti pohon. Aplikasi Terpisah. Matematika., 75 (2): 135–155, 1997

[3] Peter Damaschke. Isomorfisme subgraph yang diinduksi untuk cograph adalah NP-complete. Catatan Kuliah di Ilmu Komputer, 1991, Volume 484/1991, 72-78,

Mohammad Al-Turkistany
sumber

1

Terima kasih banyak atas jawaban Anda. Ini adalah masalah yang sangat menarik, tetapi saya pikir mereka tidak memenuhi persyaratan bahwa input hanya berupa grafik: Input pada [1] adalah grafik dan bilangan bulat, [2] grafik dan serangkaian warna untuk setiap titik, [ 3] dua grafik.

Martin Lackner

3

Berikut adalah variasi sepele dari dua masalah yang sama yang tetap NP-lengkap tetapi hanya memiliki cograph sebagai input: apakah cograph yang diberikan terdiri dari dua komponen yang terhubung, satu di antaranya merupakan subgraph yang diinduksi dari yang lain? Apakah gambar yang diberikan memiliki pewarnaan lengkap yang memberikan masing-masing simpulnya warna yang berbeda?

David Eppstein

10

$G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

vb le
sumber

2

Sekali lagi, ini dapat ditafsirkan kembali sebagai masalah pada satu cograph (yang kebetulan memiliki dua komponen yang terhubung).

David Eppstein

1

Saya melihat. Tentu saja, orang dapat meminta masalah NP-lengkap di mana input hanya terdiri dari cograph terhubung , tidak terarah, tidak tertimbang. Saya pikir, pertanyaannya cukup menarik.

vb le

1

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

David Eppstein

Ah, tidak apa-apa!

vb le

Masalah NP-hard pada cographs

Jawaban: