Subgraph isomorphism dengan pohon

Jika kita memiliki grafik besar (terarah) dan pohon berakar lebih kecil , kompleksitas apa yang paling dikenal untuk menemukan subgraf isomorfik ke ? Saya menyadari hasil isomorfisma subtree di mana dan adalah pohon dan juga di mana adalah planar atau telah terikat treewidth (dan lain-lain) tetapi tidak untuk grafik dan kasus pohon ini. $G$ $H$ $G$ $H$ $G$ $H$ $G$

ds.algorithms reference-request graph-theory Raphael
sumber

Apakah yang Anda maksudkan subgraph yang diinduksi, bukan subgraph?

Kristoffer Arnsfelt Hansen

@ Kristoffer, saya tertarik pada keduanya. Apakah saya melewatkan sesuatu yang sepele tentang kasus yang tidak diinduksi?

Raphael

Masalah Anda NP-hard bahkan jika adalah jalan, karena masalah jalan terpanjang (diinduksi atau tidak diinduksi) adalah NP-hard.

H

$H$

Yota Otachi

Iya. Saya tertarik pada apa yang lebih dikenal yang khusus untuk

menjadi pohon. Misalnya, tergantung pada properti

seperti yang ada di pertanyaan atau dengan asumsi

sudah diperbaiki dll.

H

$H$

G

$G$

H

$H$

Raphael

Masalah jalur yang diinduksi adalah W [1] -complete (Papadimitriou-Yannakakis 1991) sedangkan masalah jalur (yang tidak diinduksi) adalah FPT (Monien 1985). Lihat juga Chen-Flum 2007. Saya juga ingin mengetahui kompleksitas parameter untuk kelas pohon lainnya.

Yota Otachi

Jawaban:

Pertanyaan apakah grafik tetap adalah subgraf (terinduksi) dari adalah properti terdefinisi orde pertama, yaitu, untuk setiap ada rumus ( ) sedemikian rupa sehingga adalah subgraf (terinduksi) dari jika dan hanya jika ( ). $H$ $G$ $H$ $\varphi_H$ $\psi_H$ $H$ $G$ $G \models \varphi_H$ $G\models\psi_H$

Dahulu diketahui bahwa masalah pengecekan model adalah parameter tetap yang dapat ditelusur pada kelas grafik yang (lokal) mengecualikan minor dan pada kelas ekspansi terbatas (lokal) . Baru-baru ini, Grohe, Kreutzer dan S. mengumumkan meta-teorema yang bahkan lebih umum, yang menyatakan bahwa setiap properti orde pertama dapat diputuskan dalam waktu yang hampir linier pada kelas grafik yang padat.

Untuk pertanyaan Anda, ini menyiratkan yang berikut. Biarkan menjadi pohon berakar tetap. Maka dapat diputuskan dalam waktu linier apakah adalah subgraf (terinduksi) dari suatu input (terarah atau tidak terarah) grafik jika adalah planar, atau lebih umum adalah dari kelas yang mengecualikan minor atau dari kelas ekspansi terbatas. Masalahnya dapat diputuskan dalam waktu yang hampir linier jika berasal dari kelas yang secara lokal mengecualikan minor atau dari kelas ekspansi yang dibatasi secara lokal atau paling umum, berasal dari kelas grafik yang padat. $H$ $H$ $G$ $G$ $G$ $G$

Sebastian Siebertz
sumber

Ini dapat diselesaikan dalam waktu yang diharapkan secara acak mana adalah ukuran pohon diarahkan kecil yang dapat ditemukan dan adalah jumlah tepi grafik diarahkan besar di mana menemukannya. Lihat Teorema 6.1 dari Alon, N., Yuster, R., dan Zwick, U. (1995). Pengodean warna. J. ACM 42 (4): 844–856 . Alon et al. juga menyatakan bahwa algoritme mereka dapat derandomisasi tetapi tidak memberikan rincian untuk bagian itu; Saya pikir waktu deterministik mungkin sedikit lebih besar, sesuatu yang lebih seperti $O(2^km)$ $k$ $m$ . $O(k!\,m)$

David Eppstein
sumber

Versi derandomized harus seperti biasa, misalnya seperti cara mereka dijelaskan di bagian 4, hanya menggunakan fungsi hash sempurna untuk memetakan

node ke

color, yang menyebabkan faktor

tambahan . (juga dapat ditingkatkan menjadi faktor

, berarti benar-benar adalah

n

$n$

k

$k$

\log^{2} n

$\log^2 n$

\log n

$\log n$

O (2^{k} \cdot m \cdot \log n)

$O(2^k \cdot m \cdot \log n)$

Saeed

Anda mungkin mencari Marx, Pilipczuk bekerja pada kompleksitas parameterisasi Isomorfisme Subgraph . Secara teknis, ini hanya mencakup grafik tidak terarah, tapi saya pikir Anda dapat menyesuaikan hasil kekerasan untuk pohon dengan mudah ke pohon yang berakar. Hasil positif yang relevan untuk masalah Anda sudah dicakup oleh jawaban sebelumnya. $H$

Radu Curticapean
sumber