Jumlah maksimum lintasan panjang ganjil verteks internal yang terpisah

Misalkan $G$ adalah grafik sederhana yang tidak terarah dan misalkan menjadi simpul yang berbeda. Biarkan panjang jalur sederhana menjadi jumlah tepi di jalur. Saya tertarik untuk menghitung ukuran maksimum dari satu set jalur st sederhana sehingga setiap jalur memiliki panjang ganjil, dan set simpul dari setiap pasangan jalur berpasangan berpotongan hanya dalam s dan t. Dengan kata lain, saya mencari jumlah maksimum jalur st aneh-disjoint internal. Saya pikir ini harus polinomial-time computable oleh pencocokan atau teknik berbasis aliran, tapi saya belum bisa membuat algoritma. Inilah yang saya tahu tentang masalahnya.$s,t \in V(G)$

1. Kami dapat mengganti batasan menjadi panjang ganjil dengan panjang genap; ini tidak benar-benar mempengaruhi masalah karena satu berubah menjadi yang lain jika kita membagi semua insiden tepi pada s.

2. Jika tidak ada batasan pada paritas lintasan maka teorema Menger memberikan jawaban, yang dapat diperoleh dengan menghitung aliran maksimum.

3. Masalah menentukan jumlah maksimum siklus aneh-panjang titik-terputus-titik yang berpotongan berpasangan hanya pada titik tertentu v dapat dihitung dalam waktu polinomial dengan trik yang cocok: membangun grafik G 'sebagai persatuan disjoint dari dan , menambahkan tepi antara dua salinan dari simpul yang sama; pencocokan maksimum dalam grafik ukuran$(G - {v})$$(G - N_G[v])$$|V(G)| - |N_G[v]| + k$ menyiratkan bahwa jumlah maksimum siklus ganjil melalui$v$ adalah$k$ ; konstruksi ini dijelaskan dalam bukti Lemma 11 dariPada varian aneh-minor dugaan Hadwiger .

4. Jika grafik diarahkan maka pengujian keberadaan jalur panjang tunggal genap sudah NP-lengkap.

5. Makalah Masalah jalur-rata untuk grafik dan digraf oleh Lapaugh dan Papadimitriou mungkin relevan, tetapi sayangnya perpustakaan kami tidak berlangganan arsip online dan kami tidak memiliki salinan kertas.

Wawasan apa pun akan sangat dihargai!

Pertama catatan bahwa: diberikan grafik , dua simpul dibedakan s , t ∈ V dan integer k , masalah memutuskan apakah ada k internal vertex-disjoint aneh-panjang jalur antara s dan t adalah polynomially setara dengan memutuskan apakah ada jalur panjang k antara s dan t . Pengurangannya mudah. Untuk mengurangi dari satu kasus ke yang lain, cukup bagi setiap tepi yang berdekatan dengan t . Biarkan G $G=(V,E)$$s,t \in V$$k$$k$$s$$t$$k$$s$$t$$t$$G'$menjadi grafik yang diperoleh. Kemudian memiliki k garis putus-putus-simpul yang aneh antara s dan t jika G ′ memiliki panjang k -simpul-terputus-putus antara s dan t .$G$$k$$s$$t$$G'$$k$$s$$t$

Oleh karena itu, jika salah satu dari masalah ini adalah NP-complete, begitu juga yang lainnya. Sekarang Itai, Perl dan Shiloach menunjukkan bahwa masalah memutuskan apakah ada titik-disjoint jalur panjang lima antara s dan t adalah NP-lengkap [ Kompleksitas menemukan jalur disjoint maksimum dengan kendala panjang . Jaringan, Volume 12, Edisi 3, halaman 277-2-286, 1982.] Pengurangannya dari 3SAT dan dalam grafik yang dibangun, jalur panjang aneh antara s dan t semuanya memiliki panjang tepat lima. Karenanya masalah Vertex-Disjoint Odd Length Paths di NP-complete dan begitu juga dengan Vertex-Disjoint Even Length Paths.$k$$s$$t$$s$$t$

Semoga ini membantu.

(Ini bukan jawaban, tapi saya belum bisa berkomentar) Saya pikir jawaban di atas tidak bekerja, karena itu tidak menjamin bahwa jalurnya akan terputus-putus. Satu jalur bisa menggunakan u ', dan yang lainnya "di G'; di G mereka akan menggunakan simpul u yang sama.