Monotone bijections between lists of intervals

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

• Are there counterexamples for this greedy approach: sort the intervals of $S$ $I_1,I_2,...,I_n$ according to their decresing length; build an $n+1$ nodes tree in this way: if $I_i \subseteq I_j$ then add edge $(I_j \rightarrow I_i)$, if there are multiple intervals with the same length $I_i \subseteq I_{j_1},...,I_{j_m}$ with $|I_{j_1}|=|I_{j_2}|=...=|I_{j_m}|$ then just pick the leftmost of them and add edge $(I_{j_k} \rightarrow I_i)$. Add a root linked to the nodes having no incoming edges. Build a similar tree for $T$, then check if the two trees are isomorphic. Oct 16, 2013 at 10:27
• An interval can be included in multiple incomparable intervals, for instance [2, 3] is included in [1, 3] and [2, 4], so I think that your tree construction will not yield a tree but a directed acyclic graph. Checking if two DAGs are isomorphic (or rather embeddable in the sense I'm asking about) is NP-hard in general, I think.
– a3nm
Oct 16, 2013 at 11:30
• You're right, the above approach is not correct! Oct 16, 2013 at 17:18
• According De Biasi's answer, the problem is GI-complete when $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$. However, your post states that it is in PTIME. Which one is correct? May 8, 2018 at 18:14
• @MohammadAl-Turkistany: cf the discussion in the comments on Marzio's answer
– a3nm
May 9, 2018 at 6:30

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

• Yes, it seems that this is correct, thanks a lot! (Just a remark: the blue intervals are not required to make the reduction work, I think.) I will accept soon unless I find a reason to doubt that this reduction works.
– a3nm
Oct 17, 2013 at 11:40
• @a3nm: yes but I discovered it after drawing the figure :-). I'm still not 100% sure that there are no hidden errors in the reduction (furthermore it's the second time in two weeks that I find an NP-complete proof that uses unary 3-partition ... very strange :-) Oct 17, 2013 at 11:45
• No, it seems right: clearly a solution to 3-partition yields a solution to the interval problem. Now, going from the interval problem to the 3-partition: necessarily an interval mapping maps the red intervals to red intervals (because of the marker pyramids); same number of red intervals so interval is red iff the image by the mapping is. The markers are mapped to the right red interval (because otherwise it's a descendant, and minimality). Now if red is mapped to red and the markers are mapped as expected, the numbers have to match, so we have a correct partition. I think it makes sense!
– a3nm
Oct 17, 2013 at 11:49
• @a3nm: I saw that you accepted the answer; do you think that the result it is interesting enough to write a joint paper ? Oct 21, 2013 at 13:04
• On its own, I wouldn't think it "surprising" enough to deserve a paper... and I'm just a humble PhD student and not really in a position to offer this. For a stronger result it would be nice to compare to some tractable restriction with a non-trivial PTIME algo... I'm still wondering, e.g., what happens if $T$ is a total order, but all of the intervals have a "color" that $f$ must respect (a bit like cstheory.stackexchange.com/q/19073/4795 restricted to dimension 2)? I think it is no harder than the current problem because of a PTIME reduction, but don't know there is a tractable algo.
– a3nm
Oct 21, 2013 at 13:21