¿Una forma sencilla de determinar si un gráfico determinado es un subgrafo de algún otro gráfico?

Question

Estoy buscando un algoritmo para verificar si un gráfico determinado es un subgrafo de otro gráfico determinado.

Tengo algunas condiciones para hacer que este problema completo de NP sea un poco más factible.

• Los gráficos tienen aproximadamente <20 vértices.
• Los gráficos son DAG.
• Todos los vértices están etiquetados de forma no única y los vértices correspondientes en el gráfico principal y el subgrafo deben tener la misma etiqueta.No sé si estoy usando la terminología correcta (porque no he tomado un curso de teoría de grafos...).Será algo como:

El gráfico lineal A--B es un subgrafo de A--B--A pero A--A no es un subgrafo de A--B--A.

Cualquier sugerencia está bien.Por cierto, esta no es una pregunta de tarea.:D

Answer 1

Si las etiquetas son únicas, para un gráfico de tamaño N, existen O(N^2) Bordes, suponiendo que no hay bucles autoportados o múltiples bordes entre cada par de vértices. Usemos E Para el número de bordes.

Si hash los bordes establecidos en el gráfico principal, puede pasar por los bordes del subgrafio, verificando si cada uno está en la tabla hash (y en la cantidad correcta, si lo desea). Estás haciendo esto una vez por cada borde, por lo tanto, O(E).

Llamemos al gráfico G (con N vértices) y la posible subgraph G_1 (con M vértices), y quieres encontrar G_1 is in G.

Dado que las etiquetas no son únicas, puede, con una programación dinámica, construir los subproblemas como tales, en lugar de tener O(2^N) subproblemas, uno para cada subgrafio, tienes O(M 2^N) subproblemas: uno para cada vértice en G_1 (con M Vértices) con cada uno de los subgrafos posibles.

G_1 is in G = isSubgraph( 0, empty bitmask)

y los estados están configurados como tales:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

con el caso base siendo index = M, y puede verificar la igualdad de los bordes, dada la masa de bits (y un mapeo de etiquetas implícito). Alternativamente, también puede hacer la verificación dentro de la instrucción if: simplemente verifique que la corriente dada index, la subgraph actual G_1[0..index] es igual a G[bitmask] (con el mismo mapeo de etiqueta implícito) antes de recurrir.

Para N = 20, esto debería ser lo suficientemente rápido.

(Agregue su memorando, o puede reescribir esto con Bottoms Up DP).

Answer 2

Ok, tengo que hacer la pregunta obvia. 1. Tienes veinte vértices. Camine cada gráfico en profundidad primero, orden alfabético entre hermanos para obtener cuerdas. 2. Un gráfico es una subgraph de otra si una cadena está en otra.

Entonces, ¿qué más se esconde en la especificación del problema para que esto sea inviable?

Answer 3

Puede ver esto como un problema de alineación.Básicamente quieres crear un mapeo inyectivo. a que asigna cada vértice en V_1 a un vértice en V_2.Un mapa de alineación a se puede puntuar de la siguiente manera:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

donde \sigma(v, w, a(v), a(w)) = 1, si (a(v), a(w)) \in E_2 en caso contrario es 0.

Creo que esto se puede formular en forma de un programa lineal entero.