Équivalence d'ensemble indépendant et d'emballage d'ensemble

Selon Wikipedia, le problème de l' ensemble indépendant est un cas particulier du problème de l' ensemble de paquets . Mais il me semble que ces problèmes sont équivalents.

Le problème de recherche des ensembles indépendants est le suivant: étant donné un graphe et un entier , trouver sommets dont deux ne sont pas adjacents.$G(V,E)$$n$$n$

L' ensemble d' emballage problème de recherche est: étant donné une collection finie d'ensembles finis et un entier , trouver ensembles qui sont disjoints par paires.$C$$n$$n$

Je pense qu'ils sont équivalents sur la base de la réduction bidirectionnelle suivante:

→: Étant donné un problème d'ensemble indépendant sur un graphe , créez une collection de d'ensembles, où pour chaque sommet il y a un ensemble contenant toutes les arêtes adjacentes à . Maintenant, chaque ensemble d'emballage en correspond à un ensemble de sommets dont deux n'ont pas de bord en commun, c'est-à-dire qu'il s'agit d'un ensemble indépendant en de même taille.$G(V,E)$$C$$v \in V$$S_v \in C$$v$$C$$G$

←: Étant donné un problème d'emballage sur une collection , créez un graphe où pour chaque ensemble il y a un sommet , et il y a un bord entre et ssi les ensembles et croisent. Maintenant, chaque ensemble de sommets indépendant dans correspond à un ensemble d'ensembles de deux ne se coupent pas, c'est-à-dire qu'il s'agit d'un ensemble d'emballage en de même taille.$C$$G(V,E)$$S \in C$$v_S \in V$$v_{S_1}$$v_{S_2}$$S_1$$S_2$$G$$C$$C$

Ma question est: ma réduction est-elle correcte? Si oui, ces problèmes sont-ils équivalents? Est-il possible d'utiliser des algorithmes d'approximation pour un problème sur l'autre problème?

La signification exacte de "l'équivalent" n'est pas évidente mais vous avez montré quelque chose de plus profond que l'équivalence normale dans les réductions considérées pour les problèmes NP-complets.

Vous avez démontré ce que l'on appelle une réduction parcimonieuse entre les deux problèmes. Habituellement, les réductions entre des problèmes NP-complets sont des réductions multiples: elles n'ont la propriété que le problème A a une solution si, et seulement si, le problème B a une solution. Par exemple, lorsque vous réduisez 3SAT à 3-Colorabilité, vous produisez un graphique $G$ qui est 3-colorable si, et seulement si, la formule d'origine $\varphi$est satisfaisable. Toutefois, si$\varphi$ a $N$ variables, le nombre d'affectations satisfaisantes peut être compris entre zéro et $2^N$, inclus, alors que le nombre de 3 coloriages de tout graphique est un multiple de six en raison des permutations de l'ensemble de couleurs.

Le point au sujet des réductions parcimonieuses est qu'elles sont de un à un. Votre réduction met en place une bijection entre les solutions du problème d'ensemble indépendant et les solutions du problème d'emballage d'ensemble correspondant. Les réductions parcimonieuses sont utiles car elles préservent l'optimisation et les versions de comptage (approximatives) du problème. Donc, votre réduction montre également que le problème de trouver le plus grand ensemble indépendant est aussi difficile que de trouver l'emballage de l'ensemble en utilisant le plus d'ensembles et que le problème de compter tous les ensembles indépendants est aussi difficile que de compter tous les ensembles d'ensembles.

Il existe une classe plus large de réductions qui préservent également le comptage et le comptage approximatif. Ce sont les réductions préservant l' approximation de Dyer et al.  [1]. Ce sont des réductions oracle et assouplissent l'exigence de réduction parcimonieuse à ce qui est, essentiellement, "si vous connaissez (une approximation de) l'une, vous pouvez facilement calculer (une approximation de) l'autre". En particulier, les réductions de PA peuvent facilement faire face au facteur de $q!$ qui est inhérent à toute réduction de la $q$-problème de coloration. Comme son nom l'indique, les réductions AP préservent l'approximation, dans le sens où, s'il y a une réduction AP de A à B et qu'il y a un FPRAS pour B, il y a aussi un FPRAS pour A.

[1] Dyer, Goldberg, Greenhill, Jerrum. La complexité relative des problèmes de comptage approximatifs. Algorithmica 38 (3): 471–500, 2003. DOI ; PDF gratuit

Les deux problèmes sont NP-complets, donc même sans vérifier vos réductions, ils sont équivalents dans ce sens.

Cependant, votre réduction semble correcte. Techniquement, pour les résultats d'approximation, vous voulez vérifier certaines propriétés supplémentaires de la réduction (pas nécessairement difficile à faire, par exemple dans ce cas, les réductions PTAS sont intéressantes). Vous devez également parler des versions d'optimisation des problèmes, plutôt que des versions de décision (c'est-à-dire demander la réponse max / min, plutôt que l'existence d'une version d'une certaine taille ou plus / moins).

En fait, il est déjà connu qu'ils ont une approximation connexe. Malheureusement, ils n'ont généralement pas de bonnes approximations. Pour les deux problèmes (et Maximum Clique, qui est également étroitement lié), il y a des résultats d'inapproximabilité, le principal étant l'inapproximabilité avec $|V|^{1-\varepsilon}$ pour toute $\varepsilon > 0$ (sauf NP = ZPP), ce qui est à peu près aussi mauvais que possible.

Si vous regardez des classes restreintes de graphiques, vous pourriez trouver quelque chose d'intéressant. Pour plus de lecture, je vous renvoie au recueil inestimablement utile de Viggo Kann:

1. Emballage max.
2. Ensemble indépendant max
3. Max Clique