Y a-t-il un problème qui est facile pour le graphique cubique mais difficile pour les graphiques avec un degré maximum 3?

Les graphiques cubiques sont des graphiques où chaque sommet a un degré 3. Ils ont été largement étudiés et je suis conscient que plusieurs problèmes NP-difficiles restent NP-difficiles, même limités à des sous-classes de graphiques cubiques, mais certains deviennent plus faciles. Une superclasse de graphes cubiques est la classe de graphes de degré maximum . $\Delta \leq 3$

Y a-t-il un problème qui peut être résolu en temps polynomial pour les graphes cubiques mais qui est NP-difficile pour les graphes avec un degré maximum ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness Vinicius dos Santos
la source

Dégénérer la réponse qui montre qu'il peut y avoir différentes complexités (bien que ni NP-difficile): Trouver

est un temps constant sur les graphiques cubiques mais linéaire sur les graphiques avec

. :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

William Macrae

Bon point. :-)

Vinicius dos Santos

Pour les mauvais choix de codages, il peut même être

-hard lorsque

, mais il sera beaucoup plus utile de trouver un problème qui ne repose pas sur un mauvais codage, et encore mieux si ce problème est bien étudié une.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

William Macrae

Pour développer le commentaire de William, voici un problème artificiel. Étant donné un graphe , la séquence de degrés de , interprétée comme le codage d'une instance de 3-SAT, représente-t-elle une instance satisfaisable? $G$ $G$ (En supposant que l'encodage est tel que la séquence des 3 degrés représente une affectation satisfaisante pour chaque

.) :-)

n

$n$

Neal Young

Voir aussi cstheory.stackexchange.com/questions/1215/… pour plus d'inspiration (par exemple, les problèmes qui sont durs sur les arbres de degré maximum 3, mais triviaux s'il n'y a pas de nœuds foliaires).

Jukka Suomela

Réponses:

En voici un assez naturel: sur une entrée , déterminez si a un sous-graphe régulier connecté avec au moins fronts. Pour les graphiques à 3 normales, cela est trivial, mais si le degré maximum est 3 et que l'entrée est connectée, pas un arbre, et pas régulière, alors le plus grand sous-graphique est le cycle le plus long, donc le problème est NP-complet. $(G,k)$ $G$ $k$

David Eppstein
la source

"... alors la solution est soit le cycle le plus long soit une adaptation maximale ...". Comment votre réclamation dépend-elle de k? Ce n'est pas vrai pour tous les k.

Tyson Williams

@Tyson, il suffit que ça soit dur pour qu'un

soit dur, non? Par exemple, prenez

. David, devez-vous stipuler que le sous-graphique doit être connecté? (Sinon, toute couverture de cycle (pas seulement un cycle hamiltonien) aura

bords, et la détermination de l'existence d'une couverture de cycle se trouve dans

)

k

$k$

k = n

$k=n$

n

$n$

P

$P$

Neal Young

David, une correspondance maximale (de taille supérieure à 1) dans G n'est pas un sous-graphe connecté de G. Voulez-vous dire "... soit le cycle le plus long ou un seul bord, ..."?

Tyson Williams

OK OK. Aujourd'hui ne semble pas être un bon jour pour moi d'être rigoureux - trop de dinde probablement. J'ai ajouté un libellé pour exclure ce cas spécial.

David Eppstein

@YininCao Puisque le graphe est connecté mais pas régulier, il n'y a aucun moyen de choisir un sous-graphe à 3 réguliers. Supposons que ce soit le cas. Il existe alors un sommet qui n'a pas été sélectionné car le graphe n'est pas régulier. Puisque le graphe est connecté, ce sommet est connecté à un sommet à 3 réguliers qui a été sélectionné. Mais cela signifie qu'il existe un sommet de degré 4, une contradiction.

Tyson Williams