Réduction de la couverture de sommet à l'ensemble dominant

Question

J'essaie de réduire le problème de la couverture du sommet (décision) au problème de la décision dominante (décision) afin de prouver que ce dernier est le NP-dur. Après quelques recherches en ligne, j'ai découvert que de nombreux articles utilisent une réduction qui transforme l'entrée du problème de la couverture de sommet sur une entrée pour le problème de réglage dominant en créant un triangle pour chaque bord. ici est l'un de ces articles (voir la question 7 dans le lien).

La question que je voudrais demander est, si nous déposons des sommets isolés dans l'entrée dans le problème défini dominant, nous pourrions facilement trouver un contre-exemple à la réduction - laissez l'entrée au problème de la couverture du sommet être un graphique contenant $ n $ nœuds isolés et paramètre $ k= n $ . Maintenant, l'entrée au problème de l'ensemble dominant sera clairement un graphique vide avec le paramètre $ k= n $ . Maintenant, il y a une couverture de sommet de taille $ n $ . Mais ce n'est pas un ensemble dominant du graphe transformé (c'est-à-dire que la réponse au problème de la couverture de sommet est oui, mais la réponse au problème de la couverture définie dominante n'est pas).

Comment pourrais-je réparer la réduction? Quelqu'un pourrait-il s'il vous plaît me conseiller?

Answer 1

Si je comprends correctement, vous n'avez qu'un problème que lorsque le graphique $ g= (v, e) $ de l'instance de couverture de vertex a des sommets isolés. Dans ce cas, vous pouvez transformer $ g $ dans un graphique associé $ g '= (v \ tasse \ {x, y \}, E ') $ en ajoutant un deux nouveaux sommets $ x $ et $ y $ tel que $ x $ et $ y $ sont connectés les uns aux autres par un bord, et là est un bord entre $ x $ et l'autre vertex dans $ v $ . Formalement: $ E '= E \ CUP \ \ {(x, V) \ MID V \ in v \ tasse \ {y \} \} $

si $ g $ admet une couverture vertet $ C $ de taille au plus $ k $ , puis $ g '$ admet une couverture de sommet de taille au plus $ k + 1 $ , nommément $ c \ tasse \ {x \} $

.

.

si $ g '$ admet une couverture vertet $ C $ de taille au plus $ k + 1 $ , puis $ g $ admet une couverture de sommet de taille au plus $ K $ . Cela peut être facilement vu en remarquant que $ c \ seminus \ {x, y \} $ doit couvrir tous les bords de $ E $ , et que $ (x, y) \ in e '$ garantit au moins l'un de $ x $ et $ y $ est dans $ C $ , c'est-à-dire $ | C \ Seminus \ {x, Y \} |= | C | - | C \ Cap \ {x, Y \} | \ le | c | - 1 \ LE K $ .

puisque $ g '$ n'a pas de sommet isolé, vous pouvez maintenant le transformer en toute sécurité au graphique $ h $ < / étendue> de l'instance de réglage dominante (à l'aide de la réduction connue). De cette façon, vous montrez que $ g $ a une couverture de sommet de taille au plus $ k $ < span class="math-conteneur"> $ \ iff $ $ $ h $ a un ensemble de taille dominant au plus $ k + 1 $ .