Encontrar cadenas más largas de dispositivos a juego

Question

Set A tiene n dispositivos. El set B tiene m dispositivos. Algunos dispositivos en A son compatibles con los dispositivos en B, y algunos dispositivos en B son compatibles con los de A.

Quiero tantos dispositivos compatibles conectados entre sí como sea posible. (No es necesario que el dispositivo A en A y B en B sea mutuamente compatible).

Editar para mayor claridad: Cualquier dispositivo se puede vincular a 0, 1 o 2 dispositivos, pero no en sí mismo.

Eventualmente, todos los dispositivos (o todos menos dos, si los "extremos" no se encuentran) deben vincularse juntos 1 en 1. Es posible vincular cualquier dispositivo con cualquier otro dispositivo. Pero ningún dispositivo en A es compatible con ningún dispositivo en un vinculable), y lo mismo es cierto para los dispositivos en B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Entonces el gráfico G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

es un gráfico óptimo.

G no tiene que ser cíclico, pero puede ser.

¿Hay alguna forma inteligente de abordar esto?

Answer 1

Creo que este problema es NP-Hard por una reducción del problema de ruta más largo no dirigido, que se sabe que es NP-Hard por una reducción del problema de la ruta hamiltoniana no dirigido (ver Sipser's Introducción a la teoría del cálculo Para detalles sobre por qué).

En el problema de ruta más largo no dirigido, se nos da como entrada un gráfico no dirigido G = (V, E), junto con un par de nodos U y V y algún número K, y queremos determinar si hay o no un simple (no (no El nodo aparece dos veces) ruta de u a v de longitud al menos k. Podemos convertir esto en su problema utilizando una reducción de tiempo polinómico de la siguiente manera:

• Para cada nodo V_i ∈ V, hay un dispositivo en A (llámalo D_i).
• Para cada borde {V_i, V_j} ∈ V, hay un dispositivo en B (llámalo E_{yo, J}).
• Para cada nodo V_i y borde {V_i, V_j}, dispositivo D_i es compatible con el dispositivo e_{yo, J}.

Esta reducción tiene un tamaño polinomial, ya que el número total de dispositivos generados es de tamaño | V | + | E | y el número de conexiones es 2 | E |. Además, podemos ver que hay un camino de longitud k de V_i a V_j En el gráfico G IFF hay una cadena de dispositivos de longitud 2k + 1 de D_i a D_j. Específicamente, if ((v_i1, V_i2), (V_i2, V_i3), ..., (V_{iK - 1}, V_ik)) es un camino simple de V_i a V_j, entonces la cadena D_i1 → E_{i1, i2} → D_i2 → E_{i2, i3} → D_i3 → ... → E_{iK - 1, ik} → D_ik y viceversa. Por lo tanto, tenemos una reducción de tiempo polinómico de la ruta más larga no dirigida hacia su problema de la siguiente manera:

• Dado como entrada (G, V_i, V_j, k) al problema de ruta más largo no dirigido:
  • Construya los conjuntos A y B como se indican anteriormente, con compatibilidades C como anteriormente.
  • Verifique si hay una cadena de dispositivos de longitud 2K + 1 de D_i a D_j.
  • Si es así, salida "Sí"
  • Si no, salida "no".

Esta reducción resuelve el problema de ruta más largo no dirigido en el tiempo polinomial no determinista usando un solucionador para su problema, por lo que su problema es NP-Hard. Como resultado, no debe esperar encontrar un algoritmo de tiempo polinómico para su problema; Es probable que encontrar una respuesta exacta tome tiempo exponencial a menos que p = NP.

Lamento dar una respuesta negativa, ¡pero espero que esto ayude!

Answer 2

Esto es NP-Hard, pero creo que las aproximaciones de la cubierta de ciclo máximo pueden ayudarlo (en cada grupo de dispositivos de enlace con el borde del tamaño 0), también puede agregar un nodo adicional que se conecte a todos los demás nodos por peso 0), por ejemplo este papel: Aproximación de las cubiertas de ciclo de peso máximo en gráficos dirigidos con pesos cero y una Te ayudará.