Maximisez la distance entre k nœuds dans un graphique

8

J'ai un graphe non orienté non pondéré et je veux sélectionner nœuds dans telle sorte qu'ils soient aussi loin que possible les uns par rapport aux autres, en termes de distance géodésique . En d'autres termes, ils doivent être répartis sur le graphique autant que possible.gkg

Soit avoir la longueur d'un plus court chemin entre et dans . Maintenant, pour un ensemble de sommets , définissez (u,v)uvgXV(g)

(X)={u,v}X(u,v).

Soit le problème SCATTERED SET le problème qui sur l'entrée demande de trouver un ensemble de sommets maximisant .g,kkX(X)

Existe-t-il un algorithme efficace qui résout l'ensemble dispersé?

jbx
la source
@DW L'objectif serait de maximiser la distance entre tous les nœuds choisis. Donc, dans votre exemple, 5,5,5 serait mieux car ce serait 15. Une autre façon de voir les choses est que j'ai besoin de maximiser le nombre de nœuds intermédiaires dans le graphique que l'on devrait traverser pour éventuellement visiter tous les nœuds choisis. Vous n'êtes pas sûr du clustering, avez-vous une approche particulière en tête?
jbx
Ceci est quelque peu similaire au problème des nombres géodésiques. Un ensemble de sommetsX d'un graphique gest géodésique si chaque sommet deg se trouve sur un chemin le plus court entre deux (pas nécessairement) sommets distincts dans X. Étant donné un graphiqueg et un entier k, le problème est de décider si g a un ensemble géodésique de cardinalité au plus k. Le problème est NP-complet même pour les graphes bipartis en accords.
Juho
L'objectif peut être réécrit pour maximiser la distance moyenne.
Pål GD

Réponses:

4

Je ne sais pas s'il existe un algorithme à temps polynomial (on dirait qu'il pourrait être difficile à NP), mais voici quelques approches algorithmiques plausibles que vous pourriez envisager, si vous devez le résoudre dans la pratique:

Heuristique

Un algorithme bien exploré est Furthest Point First (FPF). À chaque itération, il choisit un point le plus éloigné de l'ensemble de points sélectionné jusqu'à présent. Répéterkfois. Comme il s'agit d'une stratégie gourmande, il n'y a aucune raison de s'attendre à ce que cela donne une réponse optimale ou même proche de l'optimale, et elle a été conçue pour optimiser une fonction objective légèrement différente ... mais dans certains contextes, elle donne une approximation raisonnable, donc cela pourrait valoir la peine d'essayer.

FPF est issu de la littérature sur le clustering basé sur les graphiques et a été présenté dans le document de recherche suivant:

Teofilo F. Gonzalez. Regroupement pour minimiser la distance maximale entre les clusters . Informatique théorique, vol 38, pp.293-306, 1985.

Vous pouvez essayer d'explorer la littérature sur le clustering basé sur des graphiques pour voir si quelqu'un a étudié votre problème spécifique.

Algorithmes exacts

Si vous rencontrez ce problème dans la pratique et avez besoin d'une solution optimale exacte, vous pouvez essayer de le résoudre à l'aide d'un solveur ILP.

Voici comment. Introduire des variables 0 ou 1Xje, où Xje indique si le jee sommet a été sélectionné, et 0 ou 1 variable yje,j, ce qui signifie que yje,j=1 seulement si Xje=1 et Xj=1. Maintenant, maximisez la fonction objectifje,j(je,j)yje,j, soumis aux contraintes Xjek et Xjeyje,j et Xjyje,j. Résolvez maintenant cet ILP avec un solveur ILP standard. Comme ILP est NP-difficile, il n'y a aucune garantie que cela sera efficace, mais cela pourrait fonctionner sur certaines instances problématiques.

Une autre approche consiste à utiliser MAX-SAT pondéré . En particulier, introduire des variables booléennesXje, où Xje est vrai si le jee sommet a été sélectionné, et les variables yje,j. La formule estϕje,jyje,j, où ϕ doit être vrai (ses clauses ont du poids W pour certains très grands W) et chaque clause yje,j est donné du poids (je,j). Définissez la formuleϕ être vrai si tout au plus k du Xjesont vraies (voir ici pour plus de détails sur la façon de le faire) et siyje,j=XjeXj pour tous je,j. Maintenant, la solution à ce problème MAX-SAT pondéré est la solution au problème d'origine, vous pouvez donc essayer de lancer un solveur MAX-SAT pondéré sur le problème. Les mêmes mises en garde s'appliquent.

DW
la source
8

Non, le problème est NP-complet.

Laisser (g,k)être une instance de INDEPENDENT SET. Constructiong en ajoutant un sommet universel u à g. L'observation cruciale est que la distance entre deux sommets dansg est 1 po g si et seulement si elles sont adjacentes get 2 sinon.

Maintenant, la solution optimale de SCATTERED SET en entrée (g,k) est 2(k2) si et seulement si g a un ensemble de taille indépendant k.

Pål GD
la source