L'isomorphisme sous-graphique induit est-il facile sur une sous-classe infinie?

Existe-t-il une séquence de graphes non dirigés , où chaque a exactement sommets et le problème $\{C_n\}_{n\in \mathbb N}$ $C_n$ $n$

Étant donné et un graphe , est-il un sous-graphe induit de ? $n$ $G$ $C_n$ $G$

est connu pour être dans la classe ? (Par exemple, lorsque , c'est le problème de clique NP-complet.) $\mathsf{P}$ $C_n=K_n$

cc.complexity-theory graph-theory sdcvvc
la source

Crosspost

sdcvvc

Donc

fait partie de la définition du problème,

fait partie de l'entrée et

fait partie de l'entrée?

{C_{n}}

$\{ C_n \}$

n

$n$

G

$G$

Andrew

@Andrew D. King: Oui.

sdcvvc

Et si

est une étoile (un nœud central connecté à

nœuds qui forment un ensemble indépendant)? pour vérifier, simplement énumérer tous les nœuds de degré

dans

, et vérifier si les voisins forment un ensemble indépendant.

C_{n}

$C_n$

n - 1

$n-1$

n - 1

$n-1$

G

$G$

Suresh Venkat

@Suresh: Il peut y avoir un sommet de degré supérieur à

, dont certains

voisins forment un ensemble indépendant. Les trouver est NP-complet.

n - 1

$n-1$

n - 1

$n-1$

sdcvvc

Réponses:

Si je ne me trompe pas, les hypothèses de complexité paramétrées modulo de Chen-Thurley-Weyer-2008 ont répondu à votre question .

Je n'ai pas encore lu attentivement le document, mais d'après ce que j'ai compris, il existe une dichotomie en ce sens que si est fini, le problème est en , mais si a un nombre infini de graphiques, l'isomorphisme de sous-graphique induit est complet (Corollaire 4, page 6). $C$ $P$ $C$ $W[1]$

Ainsi , il semble que si le premier niveau de la hiérarchie se réduit à , il n'y a pas une classe infinie de graphes dont isomorphisme sous - graphe induit est en . $W[1]$ $W$ $FPT$ $P$

Il existe un autre résultat intéressant indiquant que si alors il y a des classes pour lesquelles l'isomorphisme induit n'est ni dans ni dans complet. $P\neq NP$ $P$ $NP$

Mateus de Oliveira Oliveira
la source