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. – Marzio De Biasi Oct 16 '13 at 10:27
  • 2
    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 '13 at 11:30
  • You're right, the above approach is not correct! – Marzio De Biasi Oct 16 '13 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? – Mohammad Al-Turkistany May 8 at 18:14
  • @MohammadAl-Turkistany: cf the discussion in the comments on Marzio's answer – a3nm May 9 at 6:30
up vote 8 down vote accepted

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.

enter image description here 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 '13 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 :-) – Marzio De Biasi Oct 17 '13 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 '13 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 ? – Marzio De Biasi Oct 21 '13 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 '13 at 13:21

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.