Tamaño mínimo de contratar un DAG en un nuevo DAG

15

Tenemos un DAG Tenemos una función en los nodos (en términos generales, numeramos los nodos). Nos gustaría crear un nuevo gráfico dirigido con estas reglas:F:VN

  1. Solo los nodos con el mismo número pueden contraerse en el mismo nodo nuevo. . (Sin embargo, .)F(x)F(y)xyxyF(x)F(y)
  2. Agregamos todos los bordes antiguos entre los nuevos nodos: .(x,y)Exy(x,y)E
  3. Este nuevo gráfico sigue siendo un DAG.

¿Cuál es el mínimo? ¿Qué es un algoritmo que crea un gráfico nuevo mínimo?|VEl |

chx
fuente
1
Entonces, el problema de decisión parece ser: dado un DAG de color de vértice y un número entero , decida si hay un DAG con a lo sumo vértices formados mediante la contratación de vértices con el mismo color. kkk
András Salamon
1
Si contrae dos nodos conectados, ¿obtiene un bucle automático prohibido?
Yuval Filmus
1
No Lea 2. nuevamente: solo agregamos el borde si los dos nodos después de la contracción siguen siendo diferentes. Si dos nodos se contraen en uno, no agregamos el borde.
chx
1
@chx ¿Estás pidiendo "mínimo" o "mínimo"?
Realz Slaw
1
¿Puedes dar alguna motivación / bkg?
vzn

Respuestas:

5

Un enfoque para resolver este problema sería utilizar la programación lineal entera (ILP). Abordemos la versión de decisión del problema: dado , ¿hay alguna forma de contraer vértices del mismo color para obtener un DAG de tamaño k ?kk

Esto puede expresarse como una instancia de ILP utilizando técnicas estándar. Se nos da el color de cada vértice en el gráfico original. Sugiero que etiquetemos cada vértice con una etiqueta en ; se contraerán todos los vértices con la misma etiqueta y el mismo color. Entonces, el problema de decisión se convierte en: ¿existe un etiquetado, de modo que la contratación de todos los vértices del mismo color produzca un DAG?{1,2,...,k}

Para expresar esto como un programa lineal entero, introduzca una variable entera para cada vértice v , para representar la etiqueta en el vértice v . Suma la desigualdad 1 vk .vvv1vk

El siguiente paso es expresar el requisito de que el gráfico contratado debe ser un DAG. Tenga en cuenta que si hay un etiquetado del formulario mencionado anteriormente, sin pérdida de generalidad, existe un etiquetado en el que las etiquetas inducen una clasificación topológica en el gráfico contratado (es decir, si w en el gráfico inicial donde v , wv precede a en el gráfico contratado, entonces la etiqueta de v es más pequeño que la etiqueta de w ). Entonces, para cada borde v w en el gráfico original, agregaremos la restricción de que v y w tienen la misma etiqueta y el mismo color, o de lo contrario la etiqueta de v es más pequeña que la etiqueta de w . Específicamente, para cada borde vwvwvwvwvwvwv,w tiene el mismo color, agregue la desigualdad . Para cada arista v w donde v , w tiene diferentes colores, agregue la desigualdad v < w .vwvwv,wv<w

Ahora vea si hay alguna solución factible para este programa lineal entero. Habrá una solución factible si y solo si el etiquetado es de la forma deseada (es decir, contraer todos los vértices del mismo color produce un DAG). En otras palabras, habrá una solución factible si y solo si hay una manera de contraer el gráfico original a un DAG de tamaño . Podemos usar cualquier solucionador de programación lineal de enteros; Si el solucionador de ILP nos da una respuesta, tenemos una respuesta al problema de decisión original.k

Por supuesto, no se garantiza que esto se complete en tiempo polinómico. No hay garantías Sin embargo, los solucionadores de ILP se han vuelto bastante buenos. Esperaría que, para un gráfico de tamaño razonable, tenga una posibilidad decente de que un solucionador de ILP pueda resolver este problema en un período de tiempo razonable.

También es posible codificar esto como una instancia SAT y usar un solucionador SAT. No sé si eso sería más efectivo. Sin embargo, es probable que sea más fácil pensar en la versión ILP.

(Espero que esto sea correcto. No he revisado todos los detalles con cuidado, ¡así que por favor revise mi razonamiento! Espero no haber salido mal en alguna parte).


Actualización (21/10): Parece que los ILP de esta forma se pueden resolver en tiempo lineal, procesando el DAG en orden ordenado topológicamente y haciendo un seguimiento del límite inferior en la etiqueta para cada vértice. Esto me hace sospechar de mi solución: ¿he cometido un error en alguna parte?

DW
fuente
¡Gracias por la respuesta detallada! Recibo las restricciones y se ven razonables. Sin embargo, aunque no estoy bien versado en ILP, pensé que la programación lineal entera necesitaba una función que quisieras maximizar (o minimizar) y no la veo en ningún lado. Comprobé solo en Wikipedia, así que podría estar equivocado.
chx
@chx, estoy usando ILP para probar la viabilidad de las restricciones. Esto se puede hacer pidiéndole al solucionador de ILP que maximice cualquier función objetivo que desee (por ejemplo, maximizar 0), y luego ignore el valor de la función objetivo y solo observe si el ILP es factible o no. O bien el solucionador de ILP responde "No factible" (lo que significa que no hay un DAG contratado de tamaño ) o responde "Factible" y proporciona el mejor valor de la función objetivo que podría encontrar; en ese caso, ignora el valor de la función objetivo (y sabe que existe un DAG de tamaño k ). kk
DW
Véase, por ejemplo, engineering.purdue.edu/~engelb/abe565/… ("Solo quiero saber si existe o no una solución factible ")
DW
Con respecto a su solución de tiempo lineal; No he digerido su formulación de ILP, por lo que no puedo juzgarlo, pero estoy bastante seguro de que puedo demostrar que el problema es NP-hard, lo que haría una solución de tiempo lineal bastante útil: P. Lo publicaré pronto.
Realz Slaw
@RealzSlaw, gracias! En ese caso, sospecho fuertemente que podría haber errado en algún lugar (aunque todavía no estoy seguro de dónde).
DW
5

NOTA: AFAICT, DW encontró un agujero en esta reducción y está mal (ver comentarios). Manteniéndolo aquí por razones históricas.

Introducción : primero reduciré el problema Monotone 3SAT a nuestro problema. Aunque el problema de Monotone 3SAT es trivialmente satisfactorio, nuestro problema puede resolver aún más el problema de True Monotone 3SAT mínimo , que es NP-hard; Por lo tanto, este problema es NP-duro.

Reducción de Monotone 3SAT a nuestro problema

Tenemos una fórmula booleana monótona expresada como una secuencia de variables y una secuencia de cláusulas. El CNF tiene la forma tal que:Φ=(V,C)

y

(CyoC) Cyo=(XjXkXl)El |El |(Xj,Xk,XlV)

yo=1norteCyoEl |CyoC,norte=El |CEl |.

Conversión

Construimos un gráfico, . Cada vértice en G ' tiene una etiqueta; los vértices con la misma etiqueta son elegibles para contracción.sol=V,misol

Primero construimos el gráfico de la siguiente manera: para cada , hacemos dos nodos, cada uno etiquetado como x i , y un borde dirigido de uno a otro (haga clic en las imágenes para una vista de alta resolución).XyoVXyo

ingrese la descripción de la imagen aquí

Por supuesto, estos nodos pueden contraerse porque tienen la misma etiqueta. Consideraremos que las variables / nodos que se contratan se valoran como falsos, y los que no se contraen se valoran como verdaderos :

ingrese la descripción de la imagen aquí

V2El |VEl |CyoC, Cyo=(XjXkXl)El |Xj,Xk,XlVCyo

ingrese la descripción de la imagen aquí

Cyo1Cyo

2El |VEl |+El |CEl |

XyoXj XkCyoCyo

Aquí hay otra visualización, desenrollando la restricción de la cláusula:

ingrese la descripción de la imagen aquí

Por lo tanto, cada restricción de cláusula requiere que al menos una de las variables que contiene permanezca sin contraer; Como los nodos no contratados se valoran como verdaderos, esto requiere que una de las variables sea verdadera; exactamente lo que Monotone SAT requiere para sus cláusulas.

Reducción del mínimo verdadero monótono 3SAT

Monotone 3SAT es trivialmente satisfactorio; simplemente puede establecer todas las variables en verdadero.

Sin embargo, dado que nuestro problema de minimización de DAG es encontrar la mayoría de las contracciones, esto se traduce en encontrar la asignación satisfactoria que produce la mayoría de las variables falsas en nuestro CNF; que es lo mismo que encontrar las variables mínimas verdaderas. Este problema a veces se llama Mínimo Verdadero Monótono 3SAT o aquí (como un problema de optimización o problema de decisión), o k-True Monotone 2SAT (como un problema de decisión más débil); ambos problemas NP-difíciles. Por lo tanto, nuestro problema es NP-hard.


Referencias

Fuentes de gráficos:

Ensalada Realz
fuente
1
Guau. entonces la solución de DW debe estar equivocada (o hemos demostrado NP = P, que al menos dudo: P), pero ¿dónde?
chx
(X1X2X6 6)(X1X4 4X5 5)(X3X4 4X6 6)X1=X4 4=X6 6=Falso X2=X3=X5 5=CiertoC1X1X4 4X6 6C1
@DW También es bueno hablar con usted nuevamente: D, y buena suerte, si ambos tenemos razón, ¡podríamos tener P = NP en su respuesta! / jk
Realz Slaw
(X1,X3)
@RealzSlaw, me temo que aún no lo sigo ... No veo ninguna razón por la que mi fórmula deba ser convertida. Creo que ya es una instancia de Minimum True Monotone 3SAT. Pero déjame subirlo de nivel. En términos más generales, veo una reducción propuesta, pero no veo ningún argumento de que la reducción sea correcta, eso falta. Para que la reducción sea correcta, tiene que asignar las instancias YES a las instancias YES, y las instancias NO, a las instancias NO. Sospecho que si intenta escribir una prueba de corrección para su reducción, se encontrará con un problema cuando considere la fórmula que le di.
DW
1

Con cada reemplazo (excepto los reemplazos directos padre-hijo), agrega nuevas relaciones ancestro-descendiente que hacen que no sea trivial determinar cuál realmente vale la pena a largo plazo. Por lo tanto, un algoritmo codicioso simple fallará en el caso general. Sin embargo, si realiza un enfoque de fuerza bruta, puede determinar el gráfico más pequeño:

Python-ish (no probado):

def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph. 

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution


def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.  
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

No estoy seguro de si realmente es un problema difícil, pero jugar con algunos gráficos manualmente parece muy combinatorio. Tengo curiosidad por saber si algo difícil puede reducirse a este problema, o si hay un algoritmo con mejor tiempo de ejecución.

Ensalada Realz
fuente
1
También tengo curiosidad :)
chx