Biyecciones monótonas entre listas de intervalos

10

Tengo el siguiente problema:

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

La biyección es monótona wrt el conjunto para su inclusión en y T . X Y S , f ( X ) f ( Y )ST

XYS, f(X)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.X,Y,XYf(X)f(Y) ]

El problema está en : podemos comprobar eficientemente si una f dada es una biyección monótona.NPf

¿Existe un algoritmo de tiempo polinómico para este problema? ¿O es duro?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.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).

a3nm
fuente
S I1,I2,...,Inn+1IiIj(IjIi)IiIj1,...,Ijm|Ij1|=|Ij2|=...=|Ijm|(IjkIi)T
2
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
X,Y,XYf(X)f(Y)
@ MohammadAl-Turkistany: cf la discusión en los comentarios sobre la respuesta de Marzio
a3nm

Respuestas:

8

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

3mA={a1,a2,...,a3m}BmA1,...,AmAiB

max=ai+3m

S3m BIi3maxmaxBIiaiLBIi (línea azul en la figura).

TLm GjGjB

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).

maxBIj1,BIj2,BIj3SGjBIjkGj

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.

IiIj(IjIi)

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
Tf