Maximizar la distancia entre k nodos en un gráfico

Tengo un gráfico no ponderado no dirigido y quiero seleccionar nodos de modo que estén en pares lo más lejos posible entre sí, en términos de distancia geodésica . En otras palabras, deben extenderse alrededor del gráfico como sea posible.$G$$k$$G$

Que ser la longitud de un camino más corto entre y en . Ahora, para un conjunto de vértices , defina $d(u,v)$$u$$v$$G$$X \subseteq V(G)$

Deje que el problema CONJUNTO DISPERSO sea el problema que en la entrada $G,k$ pide encontrar un conjunto de $k$ vértices $X$ maximizando $d(X)$ .

¿Existe un algoritmo eficiente para resolver SET DISPERSO?

No sé si hay un algoritmo de tiempo polinómico (parece que podría ser NP-hard), pero aquí hay algunos enfoques algorítmicos plausibles que podría considerar, si necesita resolverlo en la práctica:

Heurística

Un algoritmo bien explorado es Furthest Point First (FPF). En cada iteración, elige un punto que está más alejado del conjunto de puntos seleccionados hasta ahora. Iterar veces. Como esta es una estrategia codiciosa, no hay razón para esperar que esto dé una respuesta óptima o incluso cercana a la óptima, y ​​fue diseñada para optimizar una función objetivo ligeramente diferente ... pero en algunos contextos ofrece una aproximación razonable, por lo que Podría valer la pena intentarlo.$k$

FPF sale de la literatura sobre agrupamiento basado en gráficos y se introdujo en el siguiente trabajo de investigación:

Teofilo F.González. Agrupación para minimizar la distancia máxima entre clústeres . Theoretical Computer Science, vol 38, pp.293-306, 1985.

Podría intentar explorar la literatura sobre agrupación basada en gráficos para ver si alguien ha estudiado su problema específico.

Algoritmos exactos

Si tiene este problema en la práctica y necesita una solución óptima exacta, puede intentar resolverlo utilizando un solucionador ILP.

Así es cómo. Introduzca las variables 0 o 1 , donde indica si se seleccionó el ésimo vértice, y las variables 0 o 1 , con el significado deseado de que solo si y . Ahora maximice la función objetivo , sujeto a las restricciones y y . Ahora resuelva este ILP con un solucionador ILP estándar. Como ILP es NP-hard, no hay garantía de que esto sea eficiente, pero podría funcionar en algunos casos problemáticos.$x_i$$x_i$$i$$y_{i,j}$$y_{i,j}=1$$x_i=1$$x_j=1$$\sum_{i,j} d(i,j) y_{i,j}$$\sum x_i \le k$$x_i \ge y_{i,j}$$x_j \ge y_{i,j}$

Otro enfoque es utilizar MAX-SAT ponderado . En particular, la introducción de variables booleanas , donde es cierto si la se seleccionó ésimo vértice, y las variables . La fórmula es , donde debe ser verdadero (sus cláusulas tienen un peso para una muy grande ) y cada cláusula se da peso . Defina la fórmula como verdadera si a lo sumo de las son verdaderas (consulte aquí para obtener detalles sobre cómo hacerlo) y si$x_i$$x_i$$i$$y_{i,j}$$\phi \land \land_{i,j} y_{i,j}$$\phi$$W$$W$$y_{i,j}$$d(i,j)$$\phi$$k$$x_i$$y_{i,j}=x_i \land x_j$ para todo . Ahora la solución a este problema de MAX-SAT ponderado es la solución al problema original, por lo que podría intentar lanzar un solucionador de MAX-SAT ponderado al problema. Se aplican las mismas advertencias.$i,j$

No, el problema es NP-completo.

Sea una instancia de CONJUNTO INDEPENDIENTE. Construir mediante la adición de un vértice universales a . La observación crucial es que la distancia entre dos vértices en es 1 en si y solo si son adyacentes en , y 2 en caso contrario.$(G,k)$$G'$$u$$G$$G$$G'$$G$

Ahora, la solución óptima de SET DISPERSO en la entrada es si y solo si tiene un conjunto independiente de tamaño .$(G',k)$$2\binom{k}{2}$$G$$k$