Quelle est la variation suivante sur la couverture de l'ensemble appelée?
Etant donné un ensemble S, une collection C de sous-ensembles de S et un entier positif K, existe-t-il K ensembles en C tels que chaque paire d'éléments de S se trouve dans l'un des sous-ensembles sélectionnés.
Remarque: Il n'est pas difficile de voir que ce problème est NP-complet: étant donné un problème de couverture de jeu normal (S, C, K), faites trois copies de S, disons S ', S' 'et S' '', puis créez vos sous-ensembles en S '' ', | S | sous-ensembles de la forme {a '} U {x en S' '| x! = a} U {a '' '}, | S | sous-ensembles de la forme {a ''} U {x dans S '| x! = a} U {a '' '}, {a', a '' | a dans C_i}. Ensuite, nous pouvons résoudre le problème de couverture d'ensemble avec K sous-ensembles ssi nous pouvons résoudre le problème de couverture de paire avec K + 1 + 2 | S | sous-ensembles.
Cela se généralise en triplets, etc. Je voudrais pouvoir ne pas perdre une demi-page à le prouver, et ce n'est probablement pas assez évident pour le rejeter comme trivial. C'est certainement suffisamment utile pour que quelqu'un l'ait prouvé, mais je n'ai aucune idée de qui ni où.
De plus, existe-t-il un bon endroit pour rechercher des résultats NP-Completeness qui ne sont pas à Garey et Johnson?
Il semble que vous généralisiez la couverture d'ensemble pour prendre en compte non seulement les éléments de S, mais tous les sous-ensembles de taille M de S. Nous pouvons énoncer le problème plus généralement:
"Étant donné un ensemble S, une collection C de sous-ensembles de S et un entier positif m, quel est le plus petit nombre d'éléments de C de telle sorte que chaque sous-ensemble taille-M de S réside dans l'un des éléments sélectionnés de C?"
En fait, cela me semble être une généralisation assez évidente de la couverture d'ensemble, et non pas celle dont vous auriez besoin pour passer du temps à prouver NP-complet au-delà d'une seule ligne. Après tout, choisir m = 1 résout le problème de couverture de l'ensemble d'origine. Peut-être que cette formulation plus générale est assez bonne pour vos besoins pour éviter d'avoir à entrer dans les détails?
Votre question sur un ensemble mis à jour de résultats d'exhaustivité de NP est bonne et mérite sa propre question. Crescenzi et Kann ont mis en ligne un recueil utile en ligne ici .
Deuxièmement, il n'est pas omniprésent, mais le manuel de conception d'algorithmes de Steven Skiena est souvent un premier arrêt utile pour un grand nombre de problèmes et est disponible en ligne en partie .
la source