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

Odpowiedzi:

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