Czy indukowany izomorfizm subgrafu jest łatwy w nieskończonej podklasie?

Czy istnieje sekwencja niekierowanych grafów , gdzie każdy ma dokładnie wierzchołków i problem $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

Biorąc pod uwagę i wykres , jest indukowanym ? $n$ $G$ $C_n$ $G$

wiadomo, że jest w klasie ? (Na przykład, gdy , jest to problem kliki NP-complete.) $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
źródło

Crosspost z cs.stackexchange.com/questions/10576

sdcvvc

Więc jest częścią definicji problemu, jest częścią danych wejściowych, a jest częścią danych wejściowych?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Andrew D. King

@Andrew D. King: Tak.

sdcvvc

Co jeśli jest gwiazdą (jeden centralny węzeł połączony z węzłami które tworzą niezależny zestaw)? aby to sprawdzić, wystarczy wymienić wszystkie węzły stopnia w i sprawdzić, czy sąsiedzi tworzą niezależny zbiór.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Suresh Venkat

@Suresh: Może istnieć wierzchołek o stopniu większym niż , którego niektórzy sąsiedzi tworzą niezależny zestaw. Znalezienie ich jest NP-zakończone.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Odpowiedzi:

Jeśli się nie mylę, na twoje pytanie odpowiedziały Chen-Thurley-Weyer-2008 modułowe założenia sparametryzowane.

Nie przeczytałem jeszcze dokładnie artykułu, ale o ile rozumiem, istnieje dychotomia w tym sensie, że jeśli jest skończone, to problem występuje w , ale jeśli ma nieskończoną liczbę wykresów, to indukowany izomorfizm subgrafu jest ukończone (wniosek 4, strona 6). $C$ $P$ $C$ $W[1]$

Tak więc wydaje się, że jeżeli na pierwszym poziomie z hierarchii zapada się , nie istnieje nieskończona grupa wykresów których indukowana subgraph Izomorfizm w . $W[1]$ $W$ $FPT$ $P$

Jest jeszcze jeden interesujący wynik stwierdzający, że jeśli to istnieją klasy, dla których indukowany izomorfizm nie jest ani w ani w całkowity. $P\neq NP$ $P$ $NP$

Mateus de Oliveira Oliveira
źródło