Pouvez-vous réduire K-Independent Set à 2-SAT

Question

Ceci est une question de devoirs pour commencer. J'ai juste quelques questions avant de commencer.

Notre problème est:

« Réduire de Set k-indépendant à 2-SAT comme suit Etant donné un graphe G avec n sommets forment des propositions n, un par sommet Chaque proposition xi pour sommet i est mis à.. vrai si le sommet i appartient à un ensemble indéfini, pour chaque arête (u, v), écris une clause qui dit que u et v ne peuvent appartenir à l'ensemble indépendant. Ma question est que tout ce que je lis dit 2-SAT n'est pas un problème NP-complet. Comment pouvons-nous réduire du problème de l'ensemble indépendant alors?

Answer 1

Il existe une différence importante entre la recherche d'un ensemble indépendant et la recherche d'un ensemble indépendant maximal (ensemble indépendant de taille maximale).

La recherche d'un ensemble indépendant se réduit bien à 2-SAT, en utilisant la réduction que vous avez décrite dans votre question. Aucun des deux problèmes n'est NP-complet. Notez que la réduction que vous avez décrite dans votre question ne limite en aucune façon le nombre de nœuds dans l'ensemble indépendant. Même l'ensemble vide satisfera le problème 2-SAT qui est produit par cette réduction, car l'ensemble vide est également un ensemble indépendant! La recherche d'un ensemble indépendant maximum (ou d'un ensemble indépendant de k) est cependant un problème NP-complet. Il ne réduit pas à 2-SAT.

Ou autrement dit: Le k dans « k -indépendante Set » est une contrainte supplémentaire qui ne fait pas partie de cette réduction de 2-SAT (c'est pourquoi le k est même pas mentionné dans la description de la réduction). Vous pouvez ajouter des clauses supplémentaires au problème SAT pour compter le nombre de nœuds inclus et faire en sorte que ce nombre soit au moins k, mais vous ne pouvez pas le faire en ajoutant seulement 2 clauses. Donc, l'ajout du k est l'étape où votre problème 2-SAT devient un problème SAT général NP-complet.

MAX-2-SAT est une extension NP-complète de 2-SAT qui peut également être utilisée pour résoudre le problème d'ensemble indépendant maximum en utilisant la réduction que vous avez affichée. (Vous auriez besoin de deux modifications triviales à la réduction: (1) Ajouter 1-clauses pour chaque proposition et (2) dupliquer les 2-clauses pour la pondération.)