Apakah ada aplikasi dekomposisi grafik modular dalam teori kompleksitas / TCS?

8

Apa yang ada beberapa aplikasi dekomposisi grafik modular dalam teori kompleksitas / TCS?

Saya terutama tertarik pada penggunaannya dalam bukti atau batas atas / bawah jika itu terjadi.

[1] Dekomposisi grafik modular , Wikipedia.

[2] Referensi untuk Dekomposisi Modular , TCS.SE.

reference-request graph-theory graph-algorithms application-of-theory cc.complexity-theory vzn
sumber
2
Habib dan Paul melakukan survei hebat pada aplikasi algoritmik dekomposisi modular: dx.doi.org/10.1016/j.cosrev.2010.01.001 . Namun, saya ragu penerapan dekomposisi modular di sisi negatif (hanya pandangan bias pribadi).
Yixin Cao
2
Dalam hasil baru-baru ini kami yang menunjukkan traktabilitas parameter dari masalah INTERVAL DELETION (untuk menghapus paling banyak simpul dari grafik beri untuk membuatnya menjadi grafik interval), grafik dekomposisi modular memang memainkan peran penting. Masalah ini memang menerima banyak minat dalam komunitas kompleksitas parameterisasi (meskipun tidak dalam komunitas kompleksitas tradisi), dan masalah yang berkaitan dengan kelas grafik adalah kandidat paling alami dari aplikasi dekomposisi modular grafik. k
Yixin Cao
@YixinCao salah satu atau keduanya bisa menjadi jawaban.
Suresh Venkat
Dekomposisi modular, atau setidaknya identifikasi klik homogen maksimal, penting untuk mendekomposisi grafik bebas-cakar. Saya juga cenderung percaya bahwa dekomposisi modular tidak berguna untuk batas bawah: Kita dapat menemukannya dengan cepat, dan begitu kita melakukannya, pada dasarnya kita memiliki pengurangan ke grafik yang lebih kecil. Jadi sebaiknya kita mulai saja dengan grafik yang lebih kecil.
Andrew D. King
1
Tesis PhD-yang disebutkan dalam jawaban ini menunjukkan tautan ke teori kompleksitas deskriptif.
frafl

Jawaban:

11

Habib dan Paul melakukan survei hebat pada aplikasi algoritmik dekomposisi modular grafik.

k

Namun, saya tidak mengetahui adanya aplikasi dekomposisi modular grafik dalam bukti batas bawah, dan saya ragu penerapannya pada sisi negatif (hanya pandangan bias pribadi).

Komentar terakhir. Sejauh yang saya tahu, sebagian besar aplikasi algoritmik tidak menggunakan kekuatan penuh dekomposisi modular grafik. Sebagai contoh, klik kritis adalah modul seri di tingkat kedua dari pohon dekomposisi modular (tingkat pertama terdiri dari setiap titik tunggal); dan kembar adalah (tidak harus kuat) modul yang terbuat dari dua simpul yang berdekatan.

Yixin Cao
sumber
Terima kasih. dari H&P online toc, bagian 7, "3 aplikasi baru dari dekomposisi modular" - pencocokan pola / interval umum dari dua permutasi, genomik komparatif / penyortiran sempurna dengan pembalikan, kompleksitas parameter dan pengurangan kernel / pengeditan klaster
vzn