Izomorfizm podsgrafu z drzewem

Jeśli mamy duży (skierowany) wykres i mniejsze ukorzenione drzewo , jaka jest najbardziej znana złożoność znajdowania podgraphów izomorficznych względem ? Zdaję sobie sprawę z wyników dla izomorfizmu poddrzewa, w którym zarówno jak i są drzewami, a także gdzie jest płaski lub ma ograniczoną szerokość (i inne), ale nie dla tego wykresu i przypadku drzewa. $G$ $H$ $G$ $H$ $G$ $H$ $G$

ds.algorithms reference-request graph-theory

— Raphael
źródło

Czy masz na myśli indukowany subgraf, zamiast subgrafu?

— Kristoffer Arnsfelt Hansen

@Kristoffer, interesuje mnie jedno i drugie. Czy przeoczyłem coś trywialnego w sprawie nie indukowanej?

— Raphael,

Twój problem jest trudny NP, nawet jeśli

jest ścieżką, ponieważ najdłuższy (indukowany lub nieindukowany) problem ścieżki jest trudny NP.

H

$H$

— Yota Otachi,

Tak. Interesuje mnie to, co wiadomo więcej, co dotyczy

który jest drzewem. Na przykład, w zależności od właściwości

takich jak te w pytaniu lub zakładając, że

jest ustalony itp.

H

$H$

G

$G$

H

$H$

— Raphael

Problemem indukowanej ścieżki jest W [1] -kompletny (Papadimitriou-Yannakakis 1991), podczas gdy (nieindukowanym) problemem ścieżki jest FPT (Monien 1985). Zobacz także Chen-Flum 2007. Chciałbym również poznać sparametryzowaną złożoność dla innych klas drzew.

— Yota Otachi,

Odpowiedzi:

Pytanie, czy jakikolwiek ustalony wykres jest (indukowanym) podrożnikiem jest definiowalną właściwością pierwszego rzędu, tj. Dla każdego istnieje wzór ( ) taki, że jest (indukowanym) podgraphem jeśli i tylko jeśli ( ). $H$ $G$ $H$ $\varphi_H$ $\psi_H$ $H$ $G$ $G \models \varphi_H$ $G\models\psi_H$

Wcześniej wiadomo było, że problem sprawdzania modelu jest możliwy do ustalenia w parametrach stałych na klasach grafów, które (lokalnie) wykluczają niewielki i na klasach (lokalnie) ekspansji ograniczonej . Niedawno Grohe, Kreutzer i S. ogłosili jeszcze bardziej ogólne meta-twierdzenie, stwierdzając, że o każdej właściwości pierwszego rzędu można decydować w prawie liniowym czasie na nigdzie gęstych klasach grafów.

W przypadku twojego pytania oznacza to, co następuje. Niech będzie unieruchomionym drzewem. Następnie można zadecydować w czasie liniowym, czy jest (indukowanym) subgrafem wejściowego (skierowanego lub nieukierowanego) wykresu jeśli jest płaski, lub bardziej ogólnie, z klasy, która wyklucza pomniejszenie lub z klasy ograniczonego rozszerzenia. Problem można rozstrzygnąć w prawie liniowym czasie, jeśli pochodzi z klasy, która lokalnie wyklucza pomniejszenie lub z klasy lokalnie ograniczonej ekspansji, lub najogólniej, pochodzi z nigdzie gęstej klasy grafów. $H$ $H$ $G$ $G$ $G$ $G$

— Sebastian Siebertz
źródło

To może być rozwiązany w randomizowanych oczekiwanego czasu , gdzie jest rozmiar małej skierowanej drzewie można znaleźć a oznacza liczbę od krawędzi dużej skierowanej wykres, na którym to znaleźć. Patrz Twierdzenie 6.1 Alon, N., Yuster, R. i Zwick, U. (1995). Kodowanie kolorami. J. ACM 42 (4): 844–856 . Alon i in. stwierdzają również, że ich algorytm można zdemandomizować, ale nie podają szczegółów tej części; Myślę, że czas deterministyczny może być nieco większy, coś bardziej jak $O(2^km)$ $k$ $m$ . $O(k!\,m)$

— David Eppstein
źródło

n

$n$

k

$k$

\log^{2} n

$\log^2 n$

\log n

$\log n$ factor, means totally is

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

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

— Saeed

You are probably looking for Marx,Pilipczuk work on parameterized complexity of Subgraph Isomorphism. Technically, it covers only undirected graphs, but I think you can adapt the hardness results for trees $H$ easily to rooted trees. The positive results relevant for your problem are already covered by the previous answers.

— Radu Curticapean
źródło