Complejidad de tipo topológico con posiciones restringidas

Se me da como entrada un DAG de vértices donde cada vértice se etiqueta adicionalmente con algo de .n x S ( x ) ⊆ { 1 , … , n $G$$n$$x$$S(x) \subseteq \{1, \ldots, n\}$

Un tipo topológico de es una biyección desde los vértices de a tal que para todos , , si hay una ruta de a en entonces . Deseo decidir si existe un tipo topológico de tal que para todo , .f G { 1 , … , n } x y x y G f ( x ) ≤ f ( y ) G x f ( x ) ∈ S ( x $G$$f$$G$$\{1, \ldots, n\}$$x$$y$$x$$y$$G$$f(x) \leq f(y)$$G$$x$$f(x) \in S(x)$

¿Cuál es la complejidad de este problema de decisión?

[Notas: Claramente esto está en NP. Si observa el gráfico de pares de vértices / posiciones permitidos, con bordes no dirigidos entre pares que entran en conflicto porque violan el orden, obtendrá un gráfico de camarillas disjuntas donde desea elegir como máximo un par por camarilla, como máximo un par por posición y, como máximo, un par por vértice: parece estar relacionado con la correspondencia tridimensional, pero no puedo ver si aún es difícil con la estructura adicional de este problema específico.]

Creo que este problema es NP-hard. Intento esbozar una reducción de MinSAT. En el problema MinSAT, se nos da un CNF y nuestro objetivo es minimizar el número de cláusulas satisfechas. Este problema es NP-hard, consulte, por ejemplo, http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Divida los vértices en dos grupos: algunos representarán literales, las otras cláusulas, por lo que donde es el número de variables del CNF (normalmente denotado por ) es el número de cláusulas. Dirija una arista desde cada vértice literal a la cláusula-vértice donde ocurre. Defina para un vértice literal que representa como (donde es un parámetro arbitrario), entonces y o y . Para cada cláusula-vértice, deje S = \ {v + 1, \ ldots, v + k, 2v + k + 1, \ ldots, n \}v n c S x i { i , i + v + k } k f ( x i ) = i f ( ˉ x i ) = i + v + k f ( ˉ x i ) = i f ( x i ) = i + v + k $n=2v+c$$v$$n$$c$$S$$x_i$$\{i,i+v+k\}$$k$$f(x_i)=i$$f(\bar x_i)=i+v+k$$f(\bar x_i)=i$$f(x_i)=i+v+k$$S=\{v+1,\ldots,v+k,2v+k+1,\ldots,n\}$, entonces $k$ de los vértices de la cláusula son `` pequeños ''.

Ahora el CNF tiene una tarea donde al menos $k$ cláusulas son falsas si y solo si su problema puede resolverse para la instancia anterior. El problema MinSAT es exactamente para probar si una fórmula CNF $\varphi$ tiene una asignación que hace que al menos $k$ cláusulas sean falsas, por lo que esto muestra que su problema es NP-hard.

Para ayudarlo a comprender esta reducción, aquí está la intuición: las etiquetas pequeñas ( ) corresponden al valor de verdad Falso, y las etiquetas grandes ( ) corresponden a cierto. Las restricciones para los vértices literales aseguran que cada sea ​​Verdadero o Falso y que tenga el valor de verdad opuesto. Los bordes aseguran que si algún literal es verdadero, todos los vértices de cláusula que lo contienen también se asignan a verdadero. (Por el contrario, si todos los literales en una cláusula se asignan a Falso, entonces esta estructura de gráfico permite asignar al vértice de la cláusula ya sea Falso o Verdadero). Finalmente, la elección de asegura que de los vértices de la cláusula se asigne a Falso y$1,2,\dots,v+k$$v+k+1,\dots,2v+k$$x_i$$\overline{x_i}$$k$$k$$c-k$de ellos se les asigna Verdadero. Entonces, si hay un tipo topológico válido de este gráfico, entonces hay una asignación a las variables que hace que al menos de las cláusulas de falsas (todos los vértices de cláusula que se asignaron a Falso, más posiblemente algunos de los los que fueron asignados Verdadero). Por el contrario, si hay una asignación a las variables que hace que al menos de las cláusulas de falsas, entonces hay un tipo topológico válido de este gráfico (rellenamos las etiquetas para los vértices literales de la manera obvia; y para cada cláusula de$k$$\varphi$$k$$\varphi$$\varphi$eso es cierto, le damos a su correspondiente cláusula-vértice una etiqueta que corresponde a Verdadero; los otros vértices de cláusula pueden recibir etiquetas correspondientes a un valor de verdad arbitrario).

Tenga en cuenta que si relaja el problema permitiendo que sea ​​arbitraria (no necesariamente biyectiva), entonces se convierte en polinomio. El algoritmo procede de manera similar a la ordenación topológica: numera los vértices uno por uno, manteniendo el conjunto U de vértices sin numerar cuyos vecinos internos han sido numerados. Siempre que sea posible, eliges un vértice x ∈ U y lo numeras con el elemento más pequeño de S ( x ) mayor que el número de sus vecinos. No es difícil ver que una instancia ( G , S ) tiene una solución si el algoritmo anterior se ejecuta en ( G $f$$U$$x \in U$$S(x)$$(G,S)$ termina con todos los vértices numerados.$(G,S)$

Una observación trivial es que si para todas las x , entonces este problema se puede resolver en tiempo polinómico, por reducción a 2SAT.$|S(x)| \le 2$$x$

Así es cómo. Introduzca una variable para cada vértice x y cada i tal que i ∈ S ( x ) . Para cada par x , y de vértices, si hay una ruta de x a y , obtenemos algunas restricciones: si i ∈ S ( x ) , j ∈ S ( y ) e i > j , entonces obtenemos la restricción ¬ v x , $v_{x,i}$$x$$i$$i \in S(x)$$x,y$$x$$y$$i\in S(x)$$j\in S(y)$$i>j$ . La bijectividad nos da otro conjunto de restricciones: para cada par x , y de vértices con x ≠ y , si i ∈ S ( x ) e i ∈ S ( y ) , sumamos ¬ v x , i ∨ ¬ v y , i . Finalmente, el requisito de que a cada vértice se le debe asignar una etiqueta nos da otro conjunto de restricciones: para cada x , si S $\neg v_{x,i} \lor \neg v_{y,j}$$x,y$$x\ne y$$i \in S(x)$$i \in S(y)$$\neg v_{x,i} \lor \neg v_{y,i}$$x$ , obtenemos la restricción v x , i ∨ v x , j . (Tenga en cuenta que solo el último conjunto de restricciones explota la promesa de que | S ( x ) | ≤ 2 para cada x .)$S(x)=\{i,j\}$$v_{x,i} \lor v_{x,j}$$|S(x)|\le 2$$x$

Me doy cuenta de que esta observación no te ayudará en tu situación particular. Lo siento por eso.