Algoritma Deterministic Parallel untuk pencocokan sempurna dalam grafik umum?

20

Dalam kelas kompleksitas , ada beberapa masalah yang diduga TIDAK berada di kelas , yaitu masalah dengan algoritma paralel deterministik. Masalah Arus Maksimum adalah salah satu contohnya. Dan ada masalah PERCAYA berada di , tetapi bukti belum ditemukan.N C N CPNCNC

Matching sempurna masalah adalah salah satu masalah mendasar yang paling mengangkat dalam teori graf: diberikan sebuah grafik , kita harus menemukan yang cocok sempurna untuk . Seperti yang dapat saya temukan di internet, terlepas dari algoritma Blossom waktu polinomial yang indah oleh Edmonds, dan algoritma paralel DIANDALISASI oleh Karp, Upfal dan Wigderson pada tahun 1986, hanya beberapa subkelas grafik yang diketahui memiliki .GGGNC

Pada Januari 2005 ada sebuah posting di blog Computational Complexity yang mengklaimnya tetap terbuka apakah Perfect Matching ada di . Pertanyaanku adalah:NC

Apakah ada kemajuan sejak itu, di luar algoritma acak ?NC

Untuk memperjelas minat saya, algoritma apa pun yang berkaitan dengan grafik UMUM bagus. Meskipun algoritma untuk subkelas grafik juga OK, itu mungkin tidak menjadi perhatian saya. Terima kasih semua!


EDIT pada 12/27:

Terima kasih atas semua bantuan Anda, saya mencoba merangkum semua hasil dalam satu gambar: Hubungan antara kelas yang terkait dengan Pencocokan

Kelas yang paling rendah diketahui mengandung masalah berikut:

  • Cocok dalam grafik umum: [ KUW86 ], [ CRS93 ]RNCRNC2
  • Pencocokan dalam bipartit planar / grafik genus konstan: / [ DKT10 ] / [ DKTV10 ]S P LUL.SPL.
  • Cocok ketika jumlah totalnya adalah polinomial: SPL. [ H09 ]
  • Pencocokan maksimal Lex-first: [ MS89 ]CC

Lebih jauh lagi, dengan asumsi kompleksitas yang masuk akal: membutuhkan sirkuit eksponensial, Pencocokan dalam grafik umum adalah dalam [ ARZ98 ].S P LSPACE[n]SPL

Hsien-Chih Chang 張顯 之
sumber
1
Mungkin tidak secara langsung relevan, tetapi ada beberapa kemajuan dalam algoritma deterministik untuk menghitung jumlah kecocokan sempurna, yaitu "Algoritma Perkiraan Deterministik Gamarnik untuk Menghitung Permanen dari matriks 0,1"
Yaroslav Bulatov
2
Ada pos terkait di sini oleh Robin Kothari: cstheory.stackexchange.com/questions/1317/…
Hsien-Chih Chang 張顯 之
@ Hsien-ChihChang 張顯 之 Bukankah L di NC yang ada di NC ^ 2 yang ada di P?
T ....

Jawaban:

13

Algoritma N C untuk pencocokan sempurna dalam grafik umum masih terbuka tetapi ada beberapa kemajuan. Berikut adalah beberapa yang saya ketahui:NC

Untuk grafik umum, Agrawal-Hoang-Thierauf menunjukkan bahwa mengingat janji bahwa jumlah kecocokan sempurna kecil, ada algoritma untuk menghitung semuanya.NC2

Untuk kelas grafik planar, pfaffia memainkan peran besar. Kastelyn menunjukkan bagaimana setiap grafik planar dapat diorientasikan sedemikian rupa sehingga pfaffian persis sama dengan jumlah pencocokan sempurna. (Ini digunakan oleh Valiant di berikan " algoritma Holographic " untuk berbagai masalah) Mahajan-Subramanya-Vinay menunjukkan bagaimana pfaffian dapat dihitung dalam menggunakan modifikasi dari urutan Clow. (Kastelyn sebenarnya memberikan algoritma untuk menemukan embedding di P tapi aku tidak yakin apakah embedding pfaffian juga dapat dihitung dalam N C ; jika ya, itu berarti bahwa matchings penghitungan sempurna dalam grafik planar adalah N C .)NCPNCNC

Dan hasil terbaru dari Vinodchandran-Tewari menunjukkan bahwa isolasi lemma bisa "derandomized" untuk grafik planar (menggunakan teorema Green!) Untuk menempatkan reachability planar di . Tapi N C algoritma untuk matchings planar masih terbuka (terima kasih kepada Raghunath untuk mengoreksi klaim saya bahwa itu adalah di U L ). Sebuah N C algoritma untuk matchings planar bipartit diberikan oleh Datta-Kulkarni-RoyUL.NCUL.NC

Semoga ini membantu.

Ramprasad
sumber
1
Ya, saya perhatikan hasilnya oleh Vinodchandran-Tewari. Bahkan, postingan ini dimotivasi oleh hasil mereka dalam beberapa cara, meskipun tidak secara langsung. Saya akan memeriksa kertas oleh Agrawal-Hoang-Thierauf!
Hsien-Chih Chang 張顯 之
10

Beberapa tahun kemudian :) dan Perfect Matching sekarang dikenal berada di Quasi-NC (yaitu, Anda perlu banyak prosesor semi-polinomi). Lihat kertas Fenner, Gurjar dan Thierauf (untuk grafik bipartit) https://arxiv.org/pdf/1601.06319.pdf dan pekerjaan kami dengan Ola Svensson (untuk grafik umum): https://arxiv.org/pdf/1704.01929

Jakub Tarnawski
sumber
8

Derandomisasi lemma isolasi oleh Tewari-Vinodchandran tidak memberikan batas atas UL pada pencocokan planar. Bahkan saya bahkan tidak berpikir algoritma NC tidak dikenal untuk pencocokan planar. Tetapi dalam sebuah karya terbaru dengan Datta, Kulkarni dan Nimbhorkar kami menunjukkan batas atas UL pada pencocokan planar bipartit (penulisan hasil ini masih dalam proses). Ini menarik karena sebelum ini bahkan ikatan NL tidak diketahui untuk masalah ini.

Raghunath Tewari
sumber
Selamat datang di TCS Stack Exchange!
Hsien-Chih Chang 張顯 之
Sekarang saya menemukan kertas karya Datta, Kulkarni dan Anda. Saya akan membacanya secepatnya, Terima kasih !!
Hsien-Chih Chang 張顯 之
7

Ketika masalah optimasi diketahui sulit, biasanya untuk melihat versi maksimalnya. Misalnya, sedangkan set independen adalah NP-Lengkap, set independen maksimal lex pertama, yang P-Lengkap.

n

Semua poin ini mengatakan bahwa mungkin tidak ada versi NC yang mudah diparalelkan untuk ini. Tapi siapa yang tahu? Seseorang dapat membatalkan pengacakan versi RNC minggu depan!

Sunting: Terima kasih Ramprasad. Tapi di sini ada tautan lain ke koran.

V Vinay
sumber
1
Ups, saya tidak punya akun untuk mengakses koran. Apa judulnya?
Hsien-Chih Chang 張顯 之
1
"Kompleksitas nilai rangkaian dan stabilitas jaringan". Saya telah meletakkan salinan makalah ini di sini: cmi.ac.in/~ramprasad/00041817.pdf (harap tidak ada masalah hak cipta!)
Ramprasad
1

(1-ϵ)-NCnΘ(1/ϵ)HAI(log3n)

T. Fischer, AV Goldberg, DJ Haglin, dan S. Plotkin. Perkiraan kecocokan secara paralel. Info Proc Lett., 46 (3): 115, 1993

Mohammad Al-Turkistany
sumber