Masalah NP-hard pada jalur

22

semua orang tahu ada banyak masalah keputusan yang NP-keras pada grafik umum, tapi saya tertarik pada masalah yang bahkan NP-keras ketika grafik yang mendasari adalah jalan. Jadi, bisakah Anda membantu saya untuk mengumpulkan masalah seperti itu?

Saya sudah menemukan pertanyaan terkait tentang masalah NP-hard pada pohon .

graph-theory np-hardness Benjamin
sumber

21

Jika Anda melihat pertanyaan itu, Anda juga harus dengan hati-hati membaca jawaban yang diterima: "Ambil masalah NP-hard apa pun yang berkaitan dengan supersekuensinya, superstring, substring, dll. Kemudian tafsirkan ulang string sebagai grafik jalur berlabel."

Saeed

2

Hanya sebuah catatan: jika jalur tidak diberi label, mereka jelas sangat dapat dikompresi dan representasi kompak adalah pilihan yang masuk akal (

bit untuk mewakili jalur

node) ... sehingga Anda juga dapat "mengubah" masalah sulit yang tidak dapat menggunakan pengkodean yang belum disahkan; misalnya bagian sum: diberikan

berlabel jalur panjang

, tidak terdapat subset dari mereka yang dapat bergabung untuk membentuk jalan panjang

?

\log n

$\log n$

n

$n$

n

$n$

a_{1}, . . ., a_{n}

$a_1,...,a_n$

b

$b$

Marzio De Biasi

24

Sebuah cocok pelangi di grafik tepi berwarna adalah pencocokan yang ujung-ujungnya memiliki warna yang berbeda. Masalahnya adalah: diberi grafik tepi-warna dan integer , apakah memiliki pelangi yang cocok dengan setidaknya tepi? Ini dikenal sebagai masalah pencocokan pelangi , dan NP- lengkapnya bahkan untuk jalur berwarna tepi yang benar. Para penulis bahkan mencatat bahwa sebelum hasil ini, tidak ada masalah grafik tidak tertimbang diketahui NP-keras untuk jalur sederhana sejauh pengetahuan mereka. $G$ $k$ $G$ $k$

Lihat Le, Van Bang, dan Florian Pfender. "Hasil kerumitan untuk pertandingan pelangi." Theoretical Computer Science (2013) , atau versi arXiv .

Juho
sumber

8

Berikut ini beberapa pengamatan sederhana.

Grafik jalur yang tidak berwarna pada dasarnya mengkode bilangan bulat, sehingga Anda dapat mengambil masalah NP-hard yang melibatkan bilangan bulat yang tidak dikodekan dan menafsirkannya kembali sebagai masalah grafik jalur. Jika Anda mengizinkan beberapa bilangan bulat yang disandikan dalam bentuk unary (= penggabungan grafik jalur), maka Anda dapat menggunakan beberapa masalah lengkap-NP seperti 3-Partition.
Grafik jalur berwarna mengkodekan sebuah kata pada alfabet tetap, jadi sekali lagi Anda bisa mengambil masalah NP-hard pada kata-kata. Contoh yang saya ketahui adalah masalah Disjoint Factors yang diperkenalkan di Bodlaender, Thomassé dan Yeo .

Super0
sumber

3

Itu pada dasarnya @ komentar Saeed ..

RB

Benar, maka jangan ragu untuk membatalkan balasan saya. Adapun masalah NP-hard pada pohon, saya bisa menyebutkan masalah Bandwidth yang terkenal; itu sebenarnya terbukti sulit untuk hierarki-W dalam sebuah laporan penelitian oleh Bodlaender, yang tidak dapat saya temukan online.

Super0

6

Motif Grafik MinCC adalah NP-hard ketika grafik adalah path (bahkan APX-hard). Diberikan grafik dengan warna pada simpul dan satu set warna, temukan subgraf yang cocok dengan set warna dan meminimalkan jumlah komputer yang terhubung. Lihat masalah Kompleksitas dalam pencocokan pola grafik berwarna titik, JDA 2011.

Olf
sumber

5

Diberikan jalur dengan simpul dan tepi berbobot , cari apakah simpul dapat dilabeli menggunakan angka di (menghindari duplikat label) sedemikian rupa sehingga perbedaan mutlak dari label dua node yang berdekatan sama dengan berat tepi: $n$ $1 \leq \text{weight}(u,v) < n$ $[1..n]$

| lab (u) - lab (v) | = weight (u, v)

$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$

Ini setara dengan masalah Rekonstruksi Permutasi dari Perbedaan yaitu NPC (salah satu hasil "tidak resmi" saya :-).

Marzio De Biasi
sumber

3

Jawaban sepele yang dekat dengan beberapa dari apa yang muncul di atas tetapi, saya pikir, berbeda.

$f\colon\mathbb{N}^3\to\mathbb{N}$ $\langle k,m,w\rangle$ $f(k,m,w)$ $m$ $w$ $n^{\log k}$ $n$ $\log k$ $k$ di unary.) Himpunan nilai itu dapat direpresentasikan sebagai himpunan path.

David Richerby
sumber

3

Masalah Aliran yang Tidak Dapat Dicabut (UFP) tetap NP-keras di jalur. Memang, UFP adalah NP-hard bahkan pada satu sisi, karena setara dengan masalah Knapsack.

Arindam Pal
sumber

3

Rainbow Dominating Set (RDS) tetap NP-hard di jalurnya. Diberikan grafik berwarna titik, RDS adalah DS di mana setiap warna grafik muncul setidaknya satu kali.

Kumpulan dominasi tropis dalam grafik berwarna titik , JDA'18

Olf
sumber

2

Set Mendominasi dan Set Mendominasi Independen adalah NP-hard pada jalur jika ada juga dalam input sebuah "grafik konflik", di mana tepi dalam grafik ini adalah sepasang simpul yang tidak dapat keduanya dalam solusi.

Cornet, Alexis; Laforest, Christian , Dominasi masalah tanpa konflik , Discrete Appl. Matematika 244, 78-88 (2018). ZBL1387.05181 .

Olf
sumber

Masalah NP-hard pada jalur

Jawaban: