Quelqu'un a-t-il déjà vu un graphique NP comme celui-ci avant?

Question

J'ai un problème de graphique suivant:

1. Entrée: entiers positifs K et L, graphique non dirigé g
2. Je dois choisir k sommets de ce graphique
3. sur le chemin entre chaque paire de kedux k choisis, il doit y avoir au moins l sommets, i.e.Il doit y avoir un "espace entre" chacun deux des sommets choisis faits d'au moins l sommets.

Ce qui précède, bien sûr peut ne pas être possible pour une instance donnée d'un problème, puis je dois vérifier cela.Je suis sûr que ce problème est NP ou même NP-complet, car il doit faire des chemins avec une contrainte de longueur.Avez-vous déjà rencontré un problème similaire?Avez-vous une idée de la façon de le réduire à un problème plus connu, éventuellement np, e.g.Couverture de sommet ou coloration graphique?

En outre, notez que mon graphique est un gril graphique, qui pourrait ne pas être "complet" mais un sous-graphique d'une grille rectangulaire complète.

Answer 1

Ceci est connu sous le nom de distance- $ d $ ensemble indépendant, c'est-à-dire que vous recherchez un ensemble indépendant de taille $ K $ où la distance entre tous les deux éléments de la solution est au moins $ d $ .

Le problème est NP-complet même sur des graphiques planaires selon [1], mais je ne connais pas sa complexité sur des grilles partielles.

En ce qui concerne les réductions, vous pouvez probablement prendre la $ D $ 'th Puissance du graphique et trouvez un ensemble indépendant (Distan-1) dans cela. La réclamation est que toute solution ici est une distance- $ d $ indépendante définie dans l'original, mais vous devez vérifier cela.

---

[1] Eto, Hiroshi, Fengrui Guo et Eiji Miyano. "Distance- $ D $ PROBLÈMES INDÉPENDANTES POUR LES GRAPHES BIPARTIST ET CHORDAL." Journal of Combinatorial Optimisation 27, no. 1 (2014): 88-99.

Answer 2

dans le cas particulier où $ l= 1 $ , il s'agit du Problème d'ensemble indépendant maximum , qui est np-dur sur des graphiques généraux. Par conséquent, votre problème est également np-dur sur les graphiques généraux.

Vous pouvez essayer d'espérer un algorithme spécifique à la classe de graphiques que vous avez (je pense que le jeu maximum indépendant Peut être calculé efficacement dans les graphiques bipartites et les graphes de grille sont bipartites. Vous pouvez donc essayer de généraliser cet algorithme), ou vous pouvez essayer d'utiliser un algorithme standard pour un ensemble / clique indépendant maximum, ou vous pouvez essayer d'utiliser un SAT. solveur. Il devrait être facile de formuler cette instance maxsat: vous avez une clause pour chaque paire de sommets qui se trouvent à distance de distance $ l + 1 $ (ou moins), et Vous demandez au solveur SAT de minimiser le nombre de variables définies à true.

Answer 3

semble être vérifiant s'il y a un sous-graphique K-sommets de G qui est colorable en utilisant les règles du problème de coloration graphique.Je veux dire si tous les keduits k sont colorés avec la même couleur qu'ils satisfont de votre état.

Depuis la coloration du graphique dans NP-complète, vous pouvez vérifier une solution donnée en temps polynomial.

Alors peut-être, juste peut-être que cela a une première vue, vous devez

1-Vérifiez si votre graphique est colorable

2-recherche d'une couleur avec un ensemble de k Vertices K / P>