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

<p>The basic idea is that disjoint intervals in $S$ like this one:</p>

<pre><code> [S]  +-a-+ +-b-+
      +---c-----+  c&lt;a, c&lt;b (here &lt; is interval inclusion)
</code></pre>

<p>can have a valid mapping to a "<em>pyramid</em>" in $T$:</p>

<pre><code> [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+    
      +-z-----+  z&lt;x, z&lt;y OK
</code></pre>

<p>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$?</p>

<p>Suppose that $max = \sum a_i + 3m$</p>

<p>We construct $S$ adding $3m$ <em>base intervals</em> $BI_i$ of length $3*max$ (red lines in the figure),
on top of each base interval  we add a <em>marker pyramid</em> of $max$ intervals of increasing length (green lines in the figure).
To base interval $BI_i$ we also add $a_i$ disjoint <em>unit intervals</em> 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).</p>

<p>Then we construct $T$ starting from a copy of $L$, then we add $m$ <em>sum groups</em> $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 <em>sum pyramid</em> of $B$ intervals of increasing length (disjoint from the marker pyramids).</p>

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

<p>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 <em>base intervals</em> ($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 <em>sum pyramid</em> of $G_j$ and cannot be "exchanged" between different groups. </p>

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

<p><img src="https://i.sstatic.net/Srfqt.jpg" alt="enter image description here">
Reduction example from the unary 3-partition problem $m=2, A = \{3,3,2,2,2,2\}, B = 7$</p>

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

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

CC BY-SA 3.0
2013-10-17T11:40:57.750Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-17T11:45:57.930Z
@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 :-)
Marzio De Biasi
CC BY-SA 3.0
2013-10-17T11:49:09.217Z
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!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-21T13:04:40.587Z
@a3nm: I saw that you accepted the answer; do you think that the result it is interesting enough to write a joint paper ?
Marzio De Biasi
CC BY-SA 3.0
2013-10-21T13:21:44.623Z
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 http://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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-28T17:59:20.097Z
Never mind, I think a variant of your proof shows hardness of the problem I was alluding to, subsuming both your original proof and the MinSAT-based proof.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-07-07T08:09:05.023Z
I have now noticed that something similar to this construction, to show hardness of a somewhat related problem from UNARY-3-PARTITION, in Warmuth and Haussler, "On the Complexity of Iterated Shuffle", JCSS, 1984 http://www.sciencedirect.com/science/article/pii/0022000084900187 (see Lemma 3.2).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-07-12T12:26:25.270Z
+1 Thank you for this elegant reduction.
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-05-08T19:57:59.730Z
@a3nm's post states that the problem is in PTIME when  $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$. However, your answer states that the problem is GI-complete.  Is my understanding correct?
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-05-09T06:29:58.113Z
@MohammadAl-Turkistany: looking closely, Marzio's answer states that the problem with the reverse condition is "no harder than GI", not that it is GI-complete. I guess what he meant is that the problem is most likely not NP-complete. And indeed, as explained in the update I added in my question, the specific DAGs that we obtain from intervals are in a restricted class (they are DAGs representing posets of dimension 2), so the problem with the reverse condition is actually in PTIME.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-16T17:15:57.717Z
2013-10-17T12:04:35.310Z
2013-10-17T12:04:35.310Z
Marzio De Biasi
<p>I have the following problem:</p>

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

<p>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)$$</p>

<p>[I am not requiring the reverse condition here. <strong><em>Update:</strong> 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 <a href="https://en.wikipedia.org/wiki/Order_dimension" rel="nofollow noreferrer">order dimension</a> 2 by construction), which is in PTIME by Möhring, <a href="http://page.math.tu-berlin.de/~moehring/adm3-scheduling/paperOrderedSets.pdf" rel="nofollow noreferrer">Computationally Tractable Classes of Ordered Sets</a>, Theorem 5.10, p. 61</em>.]</p>

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

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

<p>The question can be stated more generally as 
existence of a monotone bijection between two given posets of 
<a href="https://en.wikipedia.org/wiki/Order_dimension" rel="nofollow noreferrer">order dimension</a> 2. </p>

<p>Using a reduction inspired by the answers to <a href="https://cstheory.stackexchange.com/questions/19073/complexity-of-topological-sort-with-constrained-positions">this question</a>, 
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.</p>

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

CC BY-SA 3.0
2013-10-16T10:27:11.140Z
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.
Marzio De Biasi
CC BY-SA 3.0
2013-10-16T11:30:09.410Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-16T17:18:14.870Z
You're right, the above approach is not correct!
Marzio De Biasi
CC BY-SA 4.0
2018-05-08T18:14:09.707Z
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?
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-05-09T06:30:29.343Z
@MohammadAl-Turkistany: cf the discussion in the comments on Marzio's answer
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2018-05-09T06:54:36.533Z
Thanks for the clarification. Are you aware of a variant of this problem that is equivalent to GI? Or How can we make your problem GI-equivalent?
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-05-09T08:02:16.967Z
@MohammadAl-Turkistany: good question. A natural generalization would be to replace intervals with boxes in $\mathbb{R}^{2d}$, in which case the inclusion DAGs will correspond to posets of order dimension $2d$; but I don't know if there's a value of $d$ such that isomorphism for such DAGs is GI-complete. Other than that, you could replace intervals by some other structure. Of course, if instead of intervals we have arbitrary sets, then the inclusion DAG is just an arbitrary DAG and the problem with the reverse condition becomes isomorphism testing for arbitrary DAGs, which is GI-complete.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2018-05-09T08:08:46.323Z
Thanks again. As for you last sentence, How do we define inclusion for arbitrary sets? Can you add this case of GI-completeness to your post? It would beneficial.
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-05-09T09:35:20.013Z
@MohammadAl-Turkistany: the variant with sets would be: given two sets of sets of integers $S$ and $T$, decide if there is a bijection $f$ from $S$ to $T$ such that for any two sets $s, s' \in S$, we have $s \subseteq s'$ iff $f(s) \subseteq f(s')$. Any DAG isomorphism problem can be coded to this problem by coding each DAG as a set of sets, each vertex of the DAG being the set of its descendants (including itself). I'm not sure that this should be added to my post (it's a variant of a variant of my original question), but feel free to ask a new question about this and add this as answer. :)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2018-05-09T09:39:31.963Z
Wonderful. This does it.
Mohammad Al-Turkistany
<cc.complexity-theory><ds.algorithms><np-hardness><partial-order><matching>
Monotone bijections between lists of intervals
Antoine Amarilli 'a3nm'
# Monotone bijections between lists of intervals

(Asked by: username_0 on 2013-10-15)

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](https://en.wikipedia.org/wiki/Order_dimension) 2 by construction), which is in PTIME by Möhring, [Computationally Tractable Classes of Ordered Sets](http://page.math.tu-berlin.de/~moehring/adm3-scheduling/paperOrderedSets.pdf), 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](https://en.wikipedia.org/wiki/Order_dimension) 2.

Using a reduction inspired by the answers to [this question](https://cstheory.stackexchange.com/questions/19073/complexity-of-topological-sort-with-constrained-positions),
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).

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, partial-order, matching
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: You're right, the above approach is not correct!  
> **username_2**: 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?  
> **username_0**: @MohammadAl-Turkistany: cf the discussion in the comments on Marzio's answer  
> **username_2**: Thanks for the clarification. Are you aware of a variant of this problem that is equivalent to GI? Or How can we make your problem GI-equivalent?  
> **username_0**: @MohammadAl-Turkistany: good question. A natural generalization would be to replace intervals with boxes in $\mathbb{R}^{2d}$, in which case the inclusion DAGs will correspond to posets of order dimension $2d$; but I don't know if there's a value of $d$ such that isomorphism for such DAGs is GI-complete. Other than that, you could replace intervals by some other structure. Of course, if instead of intervals we have arbitrary sets, then the inclusion DAG is just an arbitrary DAG and the problem with the reverse condition becomes isomorphism testing for arbitrary DAGs, which is GI-complete.  
> **username_2**: Thanks again. As for you last sentence, How do we define inclusion for arbitrary sets? Can you add this case of GI-completeness to your post? It would beneficial.  
> **username_0**: @MohammadAl-Turkistany: the variant with sets would be: given two sets of sets of integers $S$ and $T$, decide if there is a bijection $f$ from $S$ to $T$ such that for any two sets $s, s' \in S$, we have $s \subseteq s'$ iff $f(s) \subseteq f(s')$. Any DAG isomorphism problem can be coded to this problem by coding each DAG as a set of sets, each vertex of the DAG being the set of its descendants (including itself). I'm not sure that this should be added to my post (it's a variant of a variant of my original question), but feel free to ask a new question about this and add this as answer. :)  
> **username_2**: Wonderful. This does it.  

---

## 1 answers

### Answer by username_1 on 2013-10-16. Score: 8 | Accepted answer

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
can have a valid mapping to a "pyramid" in $T$:
 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+    
      +-z-----+  z
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).

> **Comments:**
> **username_0**: 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.  
> **username_1**: @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 :-)  
> **username_0**: 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!  
> **username_1**: @a3nm: I saw that you accepted the answer; do you think that the result it is interesting enough to write a joint paper ?  
> **username_0**: 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 http://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.  
> **username_0**: Never mind, I think a variant of your proof shows hardness of the problem I was alluding to, subsuming both your original proof and the MinSAT-based proof.  
> **username_0**: I have now noticed that something similar to this construction, to show hardness of a somewhat related problem from UNARY-3-PARTITION, in Warmuth and Haussler, "On the Complexity of Iterated Shuffle", JCSS, 1984 http://www.sciencedirect.com/science/article/pii/0022000084900187 (see Lemma 3.2).  
> **username_2**: +1 Thank you for this elegant reduction.  
> **username_2**: @a3nm's post states that the problem is in PTIME when  $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$. However, your answer states that the problem is GI-complete.  Is my understanding correct?  
> **username_0**: @MohammadAl-Turkistany: looking closely, Marzio's answer states that the problem with the reverse condition is "no harder than GI", not that it is GI-complete. I guess what he meant is that the problem is most likely not NP-complete. And indeed, as explained in the update I added in my question, the specific DAGs that we obtain from intervals are in a restricted class (they are DAGs representing posets of dimension 2), so the problem with the reverse condition is actually in PTIME.  

---

