Monotone bijections between lists of intervals

Question

I have the following problem:

Input: two sets of intervals $S$ and $T$ (all endpoints are integers).
Query: is there a monotone bijection $f:S \to T$?

The bijection is monotone w.r.t. the set inclusion order on $S$ and $T$. $$\forall X\subseteq Y \in S, \ f(X) \subseteq f(Y)$$

[I am not requiring the reverse condition here. Update: if the reverse condition were required, i.e., $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$, then this would be in PTIME because it amounts to isomorphism testing of the corresponding inclusion posets (which have order dimension 2 by construction), which is in PTIME by Möhring, Computationally Tractable Classes of Ordered Sets, Theorem 5.10, p. 61.]

The problem is in $\mathsf{NP}$: we can check efficiently if a given $f$ is a monotone bijection.

Is there a polynomial-time algorithm for this problem? Or is it $\mathsf{NP}$-hard?

The question can be stated more generally as existence of a monotone bijection between two given posets of order dimension 2.

Using a reduction inspired by the answers to this question, I know that the problem is $\mathsf{NP}$-hard when dimensions are not restricted. However, it is not clear if the reduction would also work when dimensions are restricted.

I am also interested to know about tractability when the dimension is just bounded by some arbitrary constant (not just 2).

Answer 1

Here is an attempt to prove that the problem without the reverse condition is NP-hard.

The basic idea is that disjoint intervals in $S$ like this one:

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

can have a valid mapping to a "pyramid" in $T$:

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

The reduction is from Unary 3-Partition (which is NPC). Given $3m$ integers $A = \{a_1,a_2,...,a_{3m}\}$ and an integer $B$, does exists a partition of A in $m$ sets $A_1,...,A_m$ such that every $A_i$ have exactly 3 elements and their sum is $B$?

Suppose that $max = \sum a_i + 3m$

We construct $S$ adding $3m$ base intervals $BI_i$ of length $3*max$ (red lines in the figure), on top of each base interval we add a marker pyramid of $max$ intervals of increasing length (green lines in the figure). To base interval $BI_i$ we also add $a_i$ disjoint unit intervals of length 1 (black lines in the figure). Finally we add a long interval $L$ to cover all $BI_i$ (blue line in the figure).

Then we construct $T$ starting from a copy of $L$, then we add $m$ sum groups $G_j$, each one made with a copy of three stacked base intervals stretched in such a way that their marker pyramids don't intersect (see red+green lines at the bottom of the figure). Then we add on top of the three base intervals of $G_j$ a sum pyramid of $B$ intervals of increasing length (disjoint from the marker pyramids).

Suppose that there exists a bijection between S and T that preserves the interval inclusion (in one direction from S to T).

Then each marker pyramids of S must correspond to a marker pyramid in T (the only way to have an inclusion chain of $max$ intervals), so exactly three base intervals ($BI_{j_1},BI_{j_2},BI_{j_3}$) of $S$ must be mapped to each group $G_j$. Furthermore, the unit intervals of $BI_{j_k}$ must be mapped to the sum pyramid of $G_j$ and cannot be "exchanged" between different groups.

In a similar way it can be proved that if there exists a bijection then the original unary 3-partition problem has a solution.

Reduction example from the unary 3-partition problem $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Note: as observed in the comments the blue intervals L in S and T are not essential for the reduction.

If the reverse condition is also required, then you can build two DAGs using the relation $I_i \subseteq I_j$ to build arcs $(I_j \rightarrow I_i)$. A bijection that preserves interval inclusion in both directions exists iif the two DAGs are isomorphic. So the problem cannot be harder than the DAG isomorphism problem, which is GI-complete (and if you prove that it is NP-complete then you prove that GI is NP-complete, too).