Tipo topológico lexicográficamente mínimo de un DAG etiquetado

Considere el problema en el que se nos da como entrada un gráfico acíclico dirigido $G = (V, E)$ , una función de etiquetado $\lambda$ de $V$ a algún conjunto $L$ con un orden total $<_L$ (por ejemplo, los enteros), y donde se nos pide calcule el tipo topológico lexicográficamente más pequeño de $G$ en términos de $\lambda$ . Más precisamente, un tipo topológico de $G$ es una enumeración de $V$ como $\mathbf{v} = v_1, \ldots, v_n$, de modo que para todo $i \neq j$ , siempre que haya una ruta de $v_i$ a $v_j$ en $G$ , entonces debemos tener $i < j$ . La etiqueta de este tipo topológico es la secuencia de elementos de $S$ obtenidos como . El orden lexicográfico en tales secuencias (que tienen longitud ) se define como si hay alguna posición tal que y para todos| V | l < LEX l ′ i l i < L l ′ i l j = l ′ j j < $\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$$|V|$$\mathbf{l} <_{\text{LEX}} \mathbf{l'}$$i$$l_i <_L l_i'$$l_j = l'_j$$j < i$ . Preste atención al hecho de que cada etiqueta en puede asignarse a múltiples vértices en V (de lo contrario, el problema es trivial).$S$$V$

Este problema puede plantearse en una variante de cálculo ("calcular el tipo topológico lexicográficamente mínimo") o en una variante de decisión ("¿es esta palabra de entrada el tipo topológico mínimo?"). Mi pregunta es, ¿cuál es la complejidad de este problema ? ¿Está en PTIME (o en FP, para la variante de cálculo) o es NP-hard? Si el problema general es NP-hard, también me interesa la versión en la que el conjunto $S$ de posibles etiquetas se fija de antemano (es decir, solo hay un número constante de posibles etiquetas).

Observaciones:

Aquí hay un pequeño ejemplo del mundo real para motivar el problema. Podemos ver que el DAG representa las tareas de un proyecto (con una relación de dependencia entre ellas) y las etiquetas son enteros que representan el número de días que lleva cada tarea. Para finalizar el proyecto, me llevará la misma cantidad de tiempo total, sin importar el orden que elija para las tareas. Sin embargo, me gustaría impresionar a mi jefe, y para hacer esto quiero terminar tantas tareas como sea posible lo más rápido posible (de una manera codiciosa, incluso si eso significa ser muy lento al final porque quedan las tareas más difíciles). Elegir el orden lexicográficamente mínimo optimiza el siguiente criterio: Quiero elegir un orden tal que no haya otro orden y una cantidad de días donde despuéso ′ n n o ′ o n o ′ m < n o ′$o$$o'$$n$$n$días habría terminado más tareas con el orden que con el orden$o'$$o$ (es decir, si mi jefe mira el tiempo , daré una mejor impresión con ), pero para todos los no he terminado menos tareas con el orden que con el orden .$n$$o'$$m < n$$o'$$o$

Para dar una idea del problema: ya sé por respuestas anteriores que el siguiente problema relacionado es difícil: "¿hay algún tipo topológico que logre la siguiente secuencia"? Sin embargo, el hecho de que quiero una secuencia mínima para este orden lexicográfico parece limitar mucho los posibles órdenes topológicos que pueden lograrlo (en particular, las reducciones en esas otras respuestas ya no parecen funcionar). Intuitivamente, hay muchas menos situaciones en las que tenemos que tomar una decisión.

Tenga en cuenta que parece haber reformulaciones interesantes de los problemas en términos de cobertura de conjunto (al restringir el problema a DAG que son bipartitos, es decir, tienen altura dos): dado un conjunto de conjuntos, enumere en un orden que minimiza lexicográficamente la secuencia$S_1, \ldots, S_n$$|S_1|$,,, ,. El problema también puede reformularse en gráficos no dirigidos (expanda progresivamente un área conectada del gráfico siguiendo el orden que minimiza la secuencia lexicográfica de las etiquetas descubiertas). Sin embargo, debido al hecho de que la secuencia tiene$|S_2 \backslash S_1|$$|S_3 \backslash (S_1 \cup S_2)|$$\ldots$$|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$ para ser codicioso en todo momento por definición del orden lexicográfico, no puedo lograr que funcionen las reducciones (por ejemplo, del árbol Steiner).

¡Gracias de antemano por tus ideas!

Con múltiples copias de la misma etiqueta permitidas, el problema es NP-hard, a través de una reducción de camarillas en los gráficos. Dado un gráfico en el que desea encontrar una k -clique, haga un DAG con un vértice de origen para cada vértice de G , un vértice de sumidero para cada borde de G y un borde dirigido x y siempre que x sea ​​un vértice de G que forma un punto final del borde y . Dé a los vértices de G el valor de etiqueta 1 y los bordes de G el valor de etiqueta$G$$k$$G$$G$$xy$$x$$G$$y$$G$$1$$G$ .$0$

Entonces, hay una -clique en G si y solo si el primer orden topológico lexicográficamente forma una secuencia de k 1 's y ' s, con 's siguiendo el th . Por ejemplo, una camarilla de seis vértices estaría representada por la secuencia . Esta es la secuencia lexicográfica más pequeña que posiblemente podría comenzar un ordenamiento topológico de un DAG etiquetado dado por esta construcción (reemplazando cualquiera de los por$k$$G$$k$ $1$$\tbinom{k}{2}$ $0$$i-1$ $0$$i$$1$$110100100010000100000$$1$$0$'s daría una secuencia con más aristas de las que se podrían encontrar en un gráfico simple con tantos vértices) y solo puede ser el comienzo de un ordenamiento topológico cuando contiene la camarilla deseada.$G$

De acuerdo con esta referencia (1), el primer problema de orden topológico lexicográfico es NLOG completo.

Es posible que desee analizar más detenidamente el artículo para asegurarse de que cubre los casos que le interesan. En particular, según la versión del informe técnico (pdf) de ese artículo, parece que ' volver a tratar el orden lexicográfico de los vértices como estricto (por ejemplo: en su notación, para u ≠ v ), pero no estoy seguro de si esto afecta la aplicabilidad del resultado.$\lambda(u) \neq \lambda(v)$$u \neq v$

1. Shoudai, Takayoshi. " El primer problema de orden topológico lexicográfico es NLOG completo " . Cartas de procesamiento de información 33.3 (1989): 121-124.