Masalah optimisasi MSOL pada grafik cliquewidth terbatas, dengan predikat kardinalitas

CMSOL adalah Menghitung Monadic Second Order Logic, yaitu logika grafik di mana domain adalah himpunan simpul dan tepi, ada predikat untuk adjacency vertex-vertex dan insiden edge-vertex, ada kuantifikasi atas tepi, simpul, set tepi dan simpul set, dan ada predikat yang menyatakan apakah ukuran adalah modulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

Teorema Courcelle yang terkenal menyatakan bahwa jika adalah properti dari grafik yang dapat diekspresikan dalam CMSOL, maka untuk setiap grafik dari treewidth paling banyak dapat diputuskan dalam waktu linier apakah memegang, asalkan dekomposisi pohon diberikan dalam memasukkan. Versi teorema berikutnya menjatuhkan persyaratan bahwa dekomposisi pohon diberikan dalam input (karena seseorang dapat dihitung dengan algoritma Bodlaender ), dan juga memungkinkan pengoptimalan alih-alih hanya keputusan; yaitu diberi rumus MSOL kita juga dapat menghitung himpunan terbesar atau terkecil yang memenuhi . $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ $\phi(S)$

Pertanyaan saya menyangkut adaptasi teorema Courcelle dengan grafik cliquewidth yang dibatasi. Ada teorema yang sama mengatakan bahwa jika Anda memiliki MSOL1 yang memungkinkan kuantifikasi atas simpul, tepi, set simpul tetapi bukan set tepi kemudian diberi grafik dari cliquewidth (dengan diberikan klik-ekspresi), untuk setiap diperbaiki dapat diputuskan dalam waktu linier apakah grafik memenuhi beberapa rumus MSOL1 ; semua referensi yang saya lihat menunjuk ke $G$ $k$ $k$ $G$ $\phi$

Masalah Optimasi Terpecahkan Waktu Linear pada Grafik-Klik Lebar-Lebar oleh Courcelle, Makowsky dan Rotika, Teori Sistem Komputasi, 2000.

Saya sudah mencoba membaca makalah, tetapi tidak mandiri sehubungan dengan definisi yang tepat dari MSOL1 dan terus terang sulit untuk dibaca. Saya punya dua pertanyaan berkenaan dengan apa sebenarnya yang mungkin untuk dioptimalkan dalam FPT, parameter oleh cliquewidth grafik, jika ekspresi klik diberikan pada input.

Apakah MSOL1 mengizinkan $\textrm{Card}_{n,p}(S)$ untuk menguji ukuran set modulo sejumlah angka?
Apakah mungkin untuk menemukan set ukuran minimum / maksimum yang memenuhi formula MSOL1 $S$ $\phi(S)$ dalam FPT yang diparameterisasi oleh cliquewidth, ketika ekspresi diberikan?

Untuk kedua pertanyaan ini, saya juga ingin tahu referensi apa yang tepat untuk dikutip ketika mengklaim hasil ini. Terima kasih sebelumnya!

ds.algorithms reference-request graph-algorithms descriptive-complexity cliquewidth Bart Jansen
sumber

Saya mencoba memodifikasi beberapa artikel Anda, maaf soal itu. Karena saya cukup tertarik dengan pertanyaan Anda, tetapi masih setelah modifikasi, saya tidak yakin apakah saya memahami ide Anda dengan benar. Jadi, apakah maksud Anda bahwa Anda memerlukan definisi yang tepat tentang MSOL1, dan keberadaan predikat dan FPT dari masalah optimasi?

Hsien-Chih Chang 張顯之

M S O L_{1}

$MSOL_1$

ϕ (S)

$\phi(S)$

S

$S$

ϕ

$\phi$

_{n, p} (S)

$_{n,p}(S)$

S

$S$

ϕ (S)

$\phi(S)$

f (k) | V (G) |^{O (1)}

$f(k) |V(G)|^{O(1)}$

f

$f$

S

$S$

ϕ

$\phi$

Volume buku konsep Bruno Courcelle mungkin berguna: lihat labri.fr/perso/courcell/ActSci.html di bawah "Struktur grafik dan logika urutan kedua monadik, pendekatan teori bahasa".

András Salamon

Terima kasih; ini setidaknya menyelesaikan bagian 1) dari masalah, karena Teorema 6.4-nya di bagian pertama buku ini mengatakan: Untuk semua set hingga K dan L label vertex dan edge, masalah pengecekan model formula Counting MSOL1 diperbaiki. parameter cubic sehubungan dengan parameter cliquewidth (G) + ukuran formula.

Bart Jansen

Jawaban:

Setelah menanyakan beberapa hal lagi, tampaknya jawaban untuk 1) dan 2) keduanya YA. Mengoptimalkan kardinalitas suatu set dimungkinkan dalam LinEMSOL (sebagaimana disebutkan oleh Martin Lackner); seperti yang telah saya katakan, keberadaan predikat kardinalitas bukanlah masalah karena mereka dapat ditangani secara efisien oleh otomat pohon kondisi-terbatas, yang harus mengikuti (lebih eksplisit daripada dalam makalah yang awalnya dirujuk) dari pohon On parse dan Myhill-Nerode- ketik alat untuk menangani grafik dari lebar peringkat terbatas .

Bart Jansen
sumber

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (yang merupakan makalah yang Anda sebutkan tetapi versi yang lebih mudah dibaca) mendefinisikan LinEMSOL (Definisi 10). LinEMSOL memungkinkan untuk masalah optimasi MSO1 dan Teorema 4 menyatakan bahwa masalah-masalah tersebut dapat diperbaiki dengan parameter yang berkaitan dengan lebar klik. Jadi jawaban untuk pertanyaan / peluru kedua Anda harus ya.

Mengenai peluru pertama: Dalam "Vertex-anak di bawah umur, logika orde dua monadik, dan dugaan oleh Seese" oleh Bruno Courcelle dan Sang-il Oum penulis menulis bahwa "Dapat dibuktikan bahwa tidak ada formula MS φ (X) yang dapat mengekspresikan , dalam setiap struktur, bahwa himpunan X bahkan memiliki kardinalitas [10] "di mana [10] =" Courcelle, Logika urutan kedua monadik dari grafik "

Semoga itu bisa membantu

Martin Lackner
sumber

Terima kasih atas wawasannya, tetapi kenyataan bahwa tidak ada formula MS (secara umum) yang dapat mengungkapkan apakah suatu set memiliki kardinalitas yang benar-benar tidak relevan di sini, karena pertanyaannya adalah tentang bahasa MSol Penghitungan yang memiliki predikat khusus yang ditambahkan yang secara eksplisit memungkinkan pengujian kardinalitas. dari satu set modulo beberapa nomor tetap; oleh karena itu dalam bahasa Penghitungan MSOL dimungkinkan untuk mengekspresikan kejujuran suatu set, dan pertanyaannya adalah apakah kita dapat secara efisien menemukan set terkecil / terbesar yang memuaskan kalimat dalam Menghitung MSOL yang diparameterisasi oleh cliquewidth. Bagaimanapun, terima kasih!

Bart Jansen

Anda tentu saja benar. Saya hanya ingin menegaskan bahwa makalah yang Anda sebutkan tidak mencakup CMSOL. (Saya tidak tahu hasil yang melakukan itu.)

Martin Lackner