Kapan grafik mengakui orientasi di mana ada paling banyak satu jalan?

9

Pertimbangkan masalah berikut:

Input: grafik sederhana (tidak terarah) .G=(V,E)

Pertanyaan: Apakah ada orientasi memuaskan properti yang untuk setiap paling banyak ada satu (diarahkan) - berjalan?s , t V s tGs,tVst

Ini dapat secara ekuivalen diungkapkan sebagai:

Input: grafik sederhana (tidak terarah) .G=(V,E)

Pertanyaan: Apakah ada orientasi asiklik memuaskan properti yang untuk setiap paling banyak terdapat satu ( ) jalur - ?s , t VGs,tVtst

Apa kelas grafik yang jawabannya adalah "ya"? Bisakah masalah ini diselesaikan dalam waktu polinomial?


Beberapa pengamatan:

  1. Jika grafiknya adalah bipartit, maka jawabannya adalah "ya."
  2. Jika grafik memiliki segitiga, maka jawabannya adalah "tidak."

Pengamatan pertama mengikuti dengan mengorientasikan tepi dari satu partisi ke yang lain. Pengamatan kedua mudah untuk diperiksa. Ini membawa saya ke dua tebakan yang salah:

  1. Jawabannya adalah "ya" jika dan hanya jika grafiknya adalah bipartit. (counterexample: the 5-cycle)
  2. Jawabannya adalah "ya" jika dan hanya jika grafiknya bebas segitiga (berlawanan dengan contoh: produk kartesian tepi dengan siklus 5)
Austin Buchanan
sumber

Jawaban:

10

Ini NP-lengkap dengan pengurangan dari tidak-semua-sama-3SAT. Untuk melihat ini, perhatikan itu

  • Satu-satunya orientasi yang valid dari siklus adalah salah satu di mana tepi berganti orientasi.4
  • Misalkan adalah jalur tiga-sisi yang tidak diarahkan, dan tambahkan simpul derajat-dua yang berdekatan dengan titik akhir untuk membentuk siklus- . Maka satu-satunya orientasi yang dapat diperluas ke orientasi yang valid dari seluruh siklus adalah yang di mana tidak berorientasi secara konsisten sebagai jalur yang diarahkan.P 5 P 5 PPP5P5P

Kami membentuk gadget variabel untuk variabel yang dimiliki oleh klausa yang berbeda dari instance NAE-3SAT, dengan menempelkan bersama dibagikan sepeda di tepi yang dibagikan. Kemudian di masing-masing dari sepeda, tepi berlawanan dengan tepi bersama harus berorientasi secara konsisten dengan semua sepeda lainnya. Kami akan mengaitkan nilai kebenaran variabel dengan orientasi tepi yang konsisten ini. Selain itu, dalam setiap orientasi yang valid dari masing-masing - sepeda ini, tidak ada jalur dari satu siklus ke yang laink k 4 4 4 4 4 4vkk444444-berputar, sehingga gadget ini dapat berinteraksi satu sama lain hanya dalam orientasi tepi mereka dan tidak melalui keberadaan jalur yang lebih panjang.

Kami membentuk gadget klausa untuk klausa 3-variabel dari instance NAE-3SAT dengan menempel bersama tiga dari tepi-sepeda, berlawanan dengan tepi bersama dari tiga gadget variabel yang sesuai, ke jalur 3-tepi dan kemudian menambahkan gelar -dua vertex untuk menyelesaikan menjadi siklus. Seperti dibahas di atas, siklus ini dapat secara konsisten berorientasi jika dan hanya jika ketiga ujungnya tidak semuanya berorientasi sebagai jalur terarah, yang (bila direkatkan dengan benar) benar jika dan hanya jika nilai kebenaran yang terkait dengan orientasi ini tidak semuanya. sama.P P 5 54PP55

By the way, dags dengan paling banyak satu - berjalan untuk setiap - pasangan telah dipelajari sebelumnya, seperti "multitrees", "grafik sangat jelas", atau "bakau"; lihat https://en.wikipedia.org/wiki/Multitreet s tstst

David Eppstein
sumber
Terima kasih! Saya telah menemukan wiki multitree sebelumnya. Sepertinya mereka hampir seperti yang saya inginkan. Satu perbedaan adalah bahwa saya tidak ingin orientasi asiklik segitiga, tetapi ini adalah multitree.
Austin Buchanan
Saya ingin mengutip ini. Apakah Anda lebih suka saya mengutip sesuai jawaban Suresh di sini , atau cara lain?
Austin Buchanan
Metode dalam jawaban Suresh baik-baik saja. BTW, ulang multitrees: urutan asiklik dari segitiga adalah ok jika Anda menganggapnya sebagai hubungan biner dari urutan parsial N-bebas, tetapi tidak untuk versi DAG dari definisi, karena DAG seharusnya transitif berkurang dan segitiga asiklik tidak. Jadi saya pikir multitrees (seperti DAG) benar-benar sama dengan pertanyaan Anda.
David Eppstein