Apakah ada masalah yang mudah untuk grafik kubik tetapi sulit untuk grafik dengan derajat 3 maksimum?

Grafik kubik adalah grafik di mana setiap titik memiliki derajat 3. Mereka telah dipelajari secara ekstensif dan saya menyadari bahwa beberapa masalah NP-hard tetap NP-hard bahkan terbatas pada subkelas grafik kubik, tetapi beberapa yang lain lebih mudah. Superclass grafik kubik adalah kelas grafik dengan derajat maksimum . $\Delta \leq 3$

Apakah ada masalah yang dapat diselesaikan dalam waktu polinomial untuk grafik kubik tapi itu NP-keras untuk grafik dengan derajat maksimum ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness Vinicius dos Santos
sumber

Diturunkan jawaban yang menunjukkan mungkin ada kompleksitas yang berbeda (meskipun NP-Hard juga tidak): Menemukan adalah waktu konstan pada grafik kubik tetapi linear pada grafik dengan . :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

William Macrae

Poin bagus. :-)

Vinicius dos Santos

Untuk pilihan pengkodean yang buruk, ia bahkan bisa berupa -Bard ketika , tetapi akan jauh lebih berharga untuk menemukan masalah yang tidak bergantung pada pengkodean yang buruk, dan bahkan lebih baik jika masalah itu adalah well belajar satu.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

William Macrae

Untuk memperluas komentar William, ini adalah masalah buatan. Diberikan grafik , apakah urutan derajat , ditafsirkan sebagai pengkodean instance 3-SAT, merupakan contoh yang memuaskan? $G$ $G$

(Dengan asumsi pengkodean sedemikian rupa sehingga urutan semua-3 derajat mewakili tugas yang memuaskan untuk setiap .) :-)

n

$n$

Neal Young

Lihat juga cstheory.stackexchange.com/questions/1215/... untuk inspirasi lebih lanjut (mis., Masalah yang sulit pada pohon max 3, tetapi sepele jika tidak ada simpul daun).

Jukka Suomela

Jawaban:

Ini yang wajar: pada input , tentukan apakah memiliki subgraph reguler yang terhubung dengan setidaknya edge. Untuk grafik 3-reguler, ini sepele, tetapi jika derajat maks adalah 3 dan input terhubung, bukan pohon, dan tidak teratur, maka subgraf terbesar seperti itu adalah siklus terpanjang, sehingga masalahnya adalah NP-complete. $(G,k)$ $G$ $k$

David Eppstein
sumber

"... maka solusinya adalah siklus terpanjang atau pencocokan maksimum ...". Bagaimana klaim Anda bergantung pada k? Itu tidak benar untuk semua k.

Tyson Williams

@Tyson, itu hanya perlu sulit untuk satu menjadi keras, kan? Misalnya, ambil . David, apakah Anda perlu menetapkan bahwa subgraph harus terhubung? (Kalau tidak, setiap penutup siklus (bukan hanya siklus Hamilton) akan memiliki tepi, dan menentukan keberadaan penutup siklus dalam )

k

$k$

k = n

$k=n$

n

$n$

P

$P$

Neal Young

David, pencocokan maksimum (ukuran lebih besar dari 1) dalam G bukan subgraph yang terhubung dari G. Apakah Anda bermaksud mengatakan "... baik siklus terpanjang atau satu sisi, ..."?

Tyson Williams

Baiklah baiklah Hari ini sepertinya bukan hari yang baik bagi saya untuk bersikap keras - mungkin terlalu banyak kalkun. Saya menambahkan beberapa bahasa untuk mengesampingkan kasus khusus ini.

David Eppstein

@YininCao Karena grafik terhubung tetapi tidak teratur, tidak ada cara untuk memilih subgraf 3-reguler. Andaikan itu. Lalu ada titik yang tidak dipilih karena grafik tidak teratur. Karena grafik terhubung, simpul ini terhubung ke beberapa simpul 3-reguler yang dipilih. Tapi itu berarti ada simpul derajat 4, sebuah kontradiksi.

Tyson Williams