Największy wspólny podgraf dwóch maksymalnych wykresów płaskich

Rozważ następujący problem -

Biorąc pod uwagę maksymalne płaskie wykresy i , znajdź wykres z maksymalną liczbą krawędzi, tak że w i jest podgraph (niekoniecznie indukowany), który jest izomorficzny do $G_1$ $G_2$ $G$ $G_1$ $G_2$ $G$ .

Czy można to zrobić w czasie wielomianowym? Jeśli tak, to jak?

Wiadomo, że jeśli i są grafami ogólnymi, to problem jest NP-zupełny (ponieważ może być kliką). Wiadomo również, że jeśli i są drzewami lub częściowymi drzewami k o ograniczonym stopniu, problem można rozwiązać w czasie wielomianowym. A co z maksymalnym przypadkiem planarnym? Czy ktoś to wie? Izomorfizm grafów na dwóch maksymalnych wykresach płaskich jest wielomianowy. Może to jakoś pomaga? $G_1$ $G_2$ $G_1$ $G_1$ $G_2$

ds.algorithms graph-algorithms planar-graphs

— Vinayak Pathak
źródło

„Izomorfizm grafów na dwóch maksymalnych wykresach płaskich jest wielomianowy. Może to jakoś pomaga? Jest co najmniej powiązane (zapewne już to wiesz): istnienie wydajnego algorytmu do decydowania o izomorfizmie jest zdecydowanie niezbędnym warunkiem istnienia wydajnego algorytmu do znalezienia największego wspólnego podgrafu.

— Tsuyoshi Ito,

Tak, oczywiście. I to chyba nie wystarczy. Nie jestem zbyt pewien, ale myślę, że istnieją klasy grafów, dla których izomorfizm jest wielomianem, ale znalezienie największego wspólnego podgrupy nie jest?

— Vinayak Pathak,

Wydaje się, że problem jest

-Complete.

może być największy wspólny cykl i wiadomo, że cykl Hamiltona problemem

-Complete na maksymalne płaskich wykresów. math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf

N P

$NP$

G

$G$

N P

$NP$

— Mohammad Al-Turkistany

Jest NP-kompletny, poprzez zmodyfikowaną wersję redukcji Wigdersona zastosowaną do udowodnienia, że Hamiltoniczność maksymalnych grafów płaskich jest NP-kompletna.

Dokładne badanie dowodu twardości NP Wigdersona z 1982 r. Dla cykli hamiltonowskich na maksymalnych grafach płaskich ( http://www.math.ias.edu/avi/node/820 ) pokazuje, że instancje wywołane przez jego redukcję mają właściwość istnieje krawędź taka, że albo istnieje cykl hamiltonowski przez albo w ogóle nie istnieje żaden cykl hamiltonowski. Na przykład może być wybrane jako jedna z krawędzi w jednym z Wigdersona $e$ $e$ $e$ $M$ gadżetów Wigdersona.

Niech będzie twardą instancją skonstruowaną w ten sposób i osadzimy tak, aby krawędź należała do zewnętrznego trójkąta osadzenia. Podłączenie wielu kopii tego klipu wykresie tak, że ich -edges tworzą cykl, i aby ilość płaska ponownie wynik dodając dwie kolejne wierzchołki, na każdej stronie tego cyklu, podłączony do wszystkich odsłoniętych wierzchołków kopii . Niech liczba kopii z i wywołać otrzymanego wykresu . Niech jest liczbą wierzchołków . $G$ $G$ $e$ $e$ $G$ $c$ $H$ $n$ $G$

$(H,B)$ $B$ $H$ $c$ $H$ $c$ $2c$ $H$

$G$ $e$ $G$ $c(n+2)$ $c(n-1)$ $3c$ $G$ $c$ $3c$ $c(n-1)$ $H$ $B$ $c(n+2)$

— David Eppstein
źródło