Enumerar tipos topológicos de un DAG etiquetado con vértice

11

Deje que sea un gráfico acíclico dirigido , y dejar que λ ser una función de etiquetado mapear cada vértice v V a una etiqueta λ ( v ) en algunos finito alfabeto L . Escribiendo n : = | V | , un tipo topológico de G es una biyección σ de { 1 , ... , n } a V (es decir, un ordenamiento deG=(V,E)λvVλ(v)Ln:=|V|Gσ{1,,n}V en una secuencia) tal que siempre que ( v , v ) E entonces σ - 1 ( v ) < σ - 1 ( v ) (es decir, si hay un borde de v a v ′, entonces v ocurre antes de v en la secuencia) Laetiquetade σ es la palabra σ ( 1 ) σ ( n ) en LV(v,v)Eσ1(v)<σ1(v)vvvvσσ(1)σ(n) .Ln

Dado , me gustaría enumerar las etiquetas de los tipos topológicos de G de manera eficiente. ¿Cuál es la complejidad de enumerar las etiquetas de los tipos topológicos? Por supuesto, como puede haber exponencialmente muchos, quiero estudiar la complejidad en función del tamaño de la salida, o en términos de retraso. En particular, ¿se puede realizar la enumeración con retraso polinómico? (¿o incluso un retraso constante?)(G,λ)G

En el caso donde todos los vértices de llevan etiquetas distintas (o, de manera equivalente, los vértices están etiquetados { 1 , ... , n } por sí mismos), sé que las etiquetas se pueden enumerar en tiempo amortizado constante, por este resultado al enumerar extensiones lineales de posets (que es lo mismo que enumerar tipos topológicos de un DAG). Sin embargo, cuando los vértices se etiquetan de forma arbitraria, podría darse el caso de que una gran cantidad de tipos topológicos tengan la misma etiqueta, por lo que no puede enumerar los tipos topológicos de G y calcular sus etiquetas para obtener una manera eficiente de enumerar las etiquetas. . En terminología poset, el DAG etiquetado ( G ,G{1,,n}G puede verse como unposetetiquetado, y no pude encontrar resultados de enumeración sobre esos.(G,λ)

Ya conozco la dureza de algunos problemas relacionados gracias a las respuestas a mis otras preguntas aquí. En particular, sé que encontrar la etiqueta lexicográficamente mínima es NP-hard . También sé que decidir si una etiqueta determinada puede lograrse mediante algún tipo de topología es NP-duro (debido a la dureza de este problema : dada una secuencia de etiqueta candidata , pida un tipo topológico de G donde cada vértice debe ocurrir en una posición donde aparece la etiqueta correcta en ssGs) Sin embargo, no creo que nada de esto implique dureza para la enumeración, ya que puede enumerar en el orden que desee (no necesariamente lexicográfico), y un algoritmo de enumeración no puede usarse para decidir de manera eficiente si una etiqueta es alcanzable, incluso con retraso constante (ya que puede haber exponencialmente muchas secuencias para enumerar primero).

Tenga en cuenta que, obviamente, es fácil enumerar una primera etiqueta (simplemente tome cualquier tipo de topología). Para enumerar otra etiqueta que s , puede proceder imponiendo que algún elemento v de V se enumere en alguna posición i { 1 , ... , n } donde s iλ ( v ) : pruebe cada v e i , y verifique si G tiene un tipo topológico donde v está en la posición issvVi{1,,n}siλ(v)viGvi, que claramente se puede hacer en PTIME. Pero a medida que genera más y más etiquetas, no estoy seguro de cómo generalizar este enfoque.

a3nm
fuente

Respuestas:

-1

vuu

v1,v2,...,vkuvivju

v1,...,vkO(n2)O~(n)

sbzk
fuente
¡Gracias por tu respuesta! Sin embargo, no entiendo por qué el ajuste que sugiere en el primer párrafo sería suficiente para garantizar que se produzca una etiqueta de clasificación topológica diferente después de muchos pasos polinomiales. Por ejemplo, si todos los elementos tienen la misma etiqueta, entonces solo hay una etiqueta de clasificación topológica para enumerar, pero no estoy seguro de ver por qué su algoritmo lo notaría y terminaría lo suficientemente rápido. (Otro punto: usted dice "vecino", pero el gráfico es un DAG; ¿quiso decir "niño"?)
a3nm
El ajuste en el primer párrafo es generar todos los pedidos posibles independientemente de las etiquetas. Para limitar los ordenamientos en el caso de etiquetas similares, es importante evitar seleccionar vértices de las mismas etiquetas si parecen estar conectadas de manera similar al gráfico restante sin visitar. Por lo tanto, crearían un gráfico isomorfo no visitado que generaría el mismo orden topológico.
sbzk
O(n2)
Gracias por la explicación. Sin embargo, estoy buscando un límite polinómico en la complejidad que se aplica a todos los casos, ¡no una heurística sin garantías teóricas! :)
a3nm