Biyecciones monótonas entre listas de intervalos

Tengo el siguiente problema:

Entrada: dos conjuntos de intervalos y (todos los puntos finales son enteros). Consulta: ¿hay una biyección monótona ? $S$ $T$
$f:S \to T$

La biyección es monótona wrt el conjunto para su inclusión en y . $S$ $T$

\forall X \subseteq Y \in S, f (X) \subseteq f (Y)

$\forall X\subseteq Y \in S, \ f(X) \subseteq f(Y)$

[No estoy requiriendo la condición inversa aquí. Actualización: si se requiriera la condición inversa, es decir, , entonces esto estaría en PTIME porque equivale a la prueba de isomorfismo de los posets de inclusión correspondientes (que tienen dimensión de orden 2 por construcción), que está en PTIME por Möhring, Clases de conjuntos ordenados computacionalmente manejables , Teorema 5.10, p. 61. $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

El problema está en : podemos comprobar eficientemente si una dada es una biyección monótona. $\mathsf{NP}$ $f$

¿Existe un algoritmo de tiempo polinómico para este problema? ¿O es duro? $\mathsf{NP}$

La pregunta puede plantearse de manera más general como la existencia de una biyección monótona entre dos posets dados de dimensión de orden 2.

Utilizando una reducción inspirada en las respuestas a esta pregunta , sé que el problema es duro cuando las dimensiones no están restringidas. Sin embargo, no está claro si la reducción también funcionaría cuando las dimensiones están restringidas. $\mathsf{NP}$

También estoy interesado en saber acerca de la trazabilidad cuando la dimensión solo está limitada por alguna constante arbitraria (no solo 2).

cc.complexity-theory ds.algorithms np-hardness partial-order matching a3nm
fuente

S

$S$

I_{1}, I_{2}, . . ., I_{n}

$I_1,I_2,...,I_n$

n + 1

$n+1$

I_{i} \subseteq I_{j}

$I_i \subseteq I_j$

(I_{j} \to I_{i})

$(I_j \rightarrow I_i)$

I_{i} \subseteq I_{j_{1}}, . . ., I_{j_{m}}

$I_i \subseteq I_{j_1},...,I_{j_m}$

| I_{j_{1}} | = | I_{j_{2}} | = . . . = | I_{j_{m}} |

$|I_{j_1}|=|I_{j_2}|=...=|I_{j_m}|$

(I_{j_{k}} \to I_{i})

$(I_{j_k} \rightarrow I_i)$

T

$T$

Se puede incluir un intervalo en múltiples intervalos incomparables, por ejemplo, [2, 3] se incluye en [1, 3] y [2, 4], por lo que creo que la construcción de su árbol no producirá un árbol sino un gráfico acíclico dirigido. Verificar si dos DAG son isomórficos (o más bien integrables en el sentido en que estoy preguntando) es NP-difícil en general, creo.

a3nm

Tienes razón, el enfoque anterior no es correcto!

Marzio De Biasi

\forall X, Y, X \subseteq Y \Leftrightarrow f (X) \subseteq f (Y)

$\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$

@ MohammadAl-Turkistany: cf la discusión en los comentarios sobre la respuesta de Marzio

a3nm

Respuestas:

Aquí hay un intento de demostrar que el problema sin la condición inversa es NP-hard.

$S$

 [S]  +-a-+ +-b-+
      +---c-----+  c<a, c<b (here < is interval inclusion)

$T$

 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+    
      +-z-----+  z<x, z<y OK

$3m$ $A = \{a_1,a_2,...,a_{3m}\}$ $B$ $m$ $A_1,...,A_m$ $A_i$ $B$

$max = \sum a_i + 3m$

$S$ $3m$ $BI_i$ $3*max$ $max$ $BI_i$ $a_i$ $L$ $BI_i$ (línea azul en la figura).

$T$ $L$ $m$ $G_j$ $G_j$ $B$

Suponga que existe una biyección entre S y T que preserva la inclusión del intervalo (en una dirección de S a T).

$max$ $BI_{j_1},BI_{j_2},BI_{j_3}$ $S$ $G_j$ $BI_{j_k}$ $G_j$

De manera similar, se puede demostrar que si existe una biyección, el problema original de 3 particiones unarias tiene una solución.

ingrese la descripción de la imagen aquí $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Nota: como se observa en los comentarios, los intervalos azules L en S y T no son esenciales para la reducción.

$I_i \subseteq I_j$ $(I_j \rightarrow I_i)$

Marzio De Biasi
fuente

Sí, parece que esto es correcto, ¡muchas gracias! (Solo un comentario: creo que los intervalos azules no son necesarios para que la reducción funcione). Aceptaré pronto a menos que encuentre una razón para dudar de que esta reducción funcione.

a3nm

@ a3nm: sí, pero lo descubrí después de dibujar la figura :-). Todavía no estoy 100% seguro de que no haya errores ocultos en la reducción (además, es la segunda vez en dos semanas que encuentro una prueba completa de NP que utiliza 3 particiones unarias ... muy extraño :-)

Marzio De Biasi

No, parece correcto: claramente una solución a 3 particiones produce una solución al problema del intervalo. Ahora, pasando del problema del intervalo a la partición 3: necesariamente un mapeo de intervalos asigna los intervalos rojos a los intervalos rojos (debido a las pirámides marcadoras); mismo número de intervalos rojos, por lo que el intervalo es rojo si la imagen de la asignación es. Los marcadores se asignan al intervalo rojo correcto (porque de lo contrario es un descendiente y una minimidad). Ahora, si el rojo se asigna al rojo y los marcadores se asignan como se esperaba, los números tienen que coincidir, por lo que tenemos una partición correcta. Creo que tiene sentido!

a3nm

@ a3nm: vi que aceptaste la respuesta; ¿Crees que el resultado es lo suficientemente interesante como para escribir un artículo conjunto?

Marzio De Biasi

T

$T$

f

$f$