Montrant que la suppression minimale des sommets dans un graphe bipartite est NP-complète

Considérons le problème suivant dont l'instance d'entrée est un simple graphe et un entier naturel . $G$ $k$

Existe-t-il un ensemble tel que est biparti et ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Je voudrais montrer que ce problème est -complet en y réduisant 3-SAT, -CLIQUE, -DOMINATING SET ou -VERTEX COVER. $\rm{NP}$ $k$ $k$ $k$

Je crois que je peux y réduire le problème des 3 COULEURS, je n'aurais donc qu'à voir comment y réduire l'un des problèmes mentionnés. Mais comme ce serait plutôt compliqué, je me demande si quelqu'un voit une réduction élégante des problèmes susmentionnés.

De plus, existe-t-il un nom pour ce problème de décision?

complexity-theory np-complete reductions Jernej
la source

Transversal de cycle impair .

Pål GD

Cela semble similaire à l' ensemble de vertex de rétroaction . Autrement dit, vous voulez trouver un sous-ensemble minimum de sommets à supprimer de telle sorte que le graphique résultant soit acyclique. Un graphe acyclique est par définition un arbre (ou forêt) bipartite.

Nicholas Mancuso

@NicholasMancuso Ce n'est pas si similaire. C'est vraiment, comme je l'ai dit plus haut, le problème transversal du cycle impair. Ou, comme le souligne Vor, Yannakakis a appelé la suppression du nœud bipartite (ou sommet) dans les années 70 et 80.

Pål GD

@ PålGD, je suis d'accord. Je pensais que la réduction la plus simple proviendrait de FVS. Cependant, cela est rendu inutile par sa définition de cycle impair.

Nicholas Mancuso

@Jernej: vous dites "... je voudrais montrer que ce problème est en NP en le réduisant soit en 3-SAT, le k-CLIQUE, ...". Vous voulez dire "je voudrais montrer que ce problème est NP-difficile en utilisant une réduction de 3-SAT, k-CLIQUE, ..."? (le problème est clairement dans NP car tester si un graphe est bipartite peut être fait en temps linéaire)

Vor

Réponses:

Votre problème est un cas particulier d'une classe plus large de problèmes nommés problèmes de suppression de nœuds :

JM Lewis et M. Yannakakis, "Le problème de suppression de nœuds pour les propriétés héréditaires est NP-complet"

... Cet article traite de la classe des problèmes de graphes définis comme suit:
pour une propriété de graphe fixe , trouver le nombre minimum de nœuds (ou sommets) qui doivent être supprimés d'un graphe donné pour que le résultat satisfasse . Nous appelons cela le problème de suppression de nœuds pour . Nos résultats montrent que si est une propriété non triviale héréditaire sur le sous-graphe induit, alors le problème de suppression de noeud pour est NP-difficile. De plus, si nous ajoutons la condition que le test de $\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ peut être effectuée en temps polynomial, alors nos résultats impliquent que le problème de suppression de noeud pour est NP-complet. ... $\Pi$

Votre problème est le problème de suppression de noeud pour la bipartité , mais (comme l'a noté Pal), il est connu aujourd'hui sous le nom de problème de traversée de cycle impair (OCT).

ÉDITER

Pour ce qui concerne une réduction directe, j'ai pensé à celle de 3SAT.

Étant donné une instance de 3SAT avec variables et clauses, construisez le graphique suivant: ajoutez deux nœuds pour chaque variable et un bord entre eux. Pour simuler une affectation de vérité, ajoutez nœuds pour chaque variable et connectez-les tous les deux à et ; de cette façon, pour faire un graphe bipartite supprimant au plus nœuds, au moins un entre et doit être supprimé. Enfin pour chaque clause ajoutez 4 nœuds et construisez un cycle impair qui relie les variables dans . $n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ $C_j$ $C_j$

Le graphe résultant peut être rendu bipartite en supprimant au plus nœuds si et seulement si la formule 3SAT d'origine est satisfaisable. $G$ $n$

entrez la description de l'image ici

Vor
la source

Ce n'est pas vraiment la réponse que la question demande. OP veut réduire explicitement en utilisant le problème donné. De plus, le problème est connu aujourd'hui sous le nom de cycle de cycle impair.

Pål GD

@ PålGD: vous avez raison.

Vor

Oui, mais je ne vois pas immédiatement une réduction de la liste des problèmes de OP, cependant ... Je ne connais que celui que vous mentionnez, par Yannakakis.

Pål GD

@ PålGD: Je vais penser à une réduction différente, mais pour être honnête, je ne suis pas sûr de ce que veut exactement le PO (voir mon commentaire ci-dessus).

Vor

@ Pour ce que je veux, c'est voir une réduction simple à l'un de l'un des problèmes mentionnés. Cet article m'est connu mais je recherche plutôt la réduction la plus directe.

Jernej