Monotonia bijections między listami interwałów

Mam następujący problem:

Dane wejściowe: dwa zestawy przedziałów i (wszystkie punkty końcowe są liczbami całkowitymi). Pytanie: czy istnieje biotonia monotoniczna ?T f : S → $S$$T$
$f:S \to T$

Bijection jest monotoniczne WRT kolejnością włączenie do i . T ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y $S$$T$

[Nie wymagam tutaj odwrotnego warunku. Aktualizacja: jeśli wymagane byłyby warunki odwrotne, tj. , to byłoby to w trybie PTIME, ponieważ sprowadza się to do testowania izomorfizmu odpowiedniego włączenia zestawy (które mają wymiar rzędu 2 według konstrukcji), które są w PTIME według Möhringa, klasy obliczalne zbiorów uporządkowanych , Twierdzenie 5.10, str. 61.$\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

Problem tkwi w : możemy skutecznie sprawdzić, czy dane jest biotonią monotoniczną.$\mathsf{NP}$$f$

Czy istnieje algorytm czasu wielomianowego dla tego problemu? A może to twardy?$\mathsf{NP}$

Pytanie to można sformułować bardziej ogólnie jako istnienie monotonicznego bijectionu między dwoma danymi zestawami wymiaru porządku 2.

Korzystając z redukcji zainspirowanej odpowiedziami na to pytanie , wiem, że problemem jest twardy, gdy wymiary nie są ograniczone. Nie jest jednak jasne, czy redukcja działałaby również, gdy wymiary są ograniczone.$\mathsf{NP}$

Interesuje mnie również wiedza na temat podatności na rozciąganie, gdy wymiar jest po prostu ograniczony dowolną stałą (nie tylko 2).

Oto próba udowodnienia, że ​​problem bez odwrotnego warunku jest trudny do NP.

Podstawową ideą jest to, że rozłączne interwały w takie:$S$

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

może mieć prawidłowe odwzorowanie na „ piramidę ” w :$T$

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

Redukcja pochodzi z Unary 3-Partition (czyli NPC). Biorąc pod uwagę, całkowite = { 1 , 2 , . . . , 3 m } i całkowita B , nie występuje podział A w m zestawów 1 , . . . , M takie, że każdy i mają dokładnie 3 pierwiastki i ich suma jest B ?$3m$$A = \{a_1,a_2,...,a_{3m}\}$$B$$m$$A_1,...,A_m$$A_i$$B$

Załóżmy, że $max = \sum a_i + 3m$

konstruujemy S dodając 3 m przedziały bazowe B I i o długości 3 ∗ m a x (czerwone linie na rysunku), na szczycie każdego przedziału podstawowego dodajemy piramidę znacznikową o odstępach m a x o coraz większej długości (zielone linie w postać). Do podstawowego przedziału B I i dodajemy również i rozłączne przedziały jednostkowe o długości 1 (czarne linie na rysunku). Na koniec dodajemy długi odstęp L, aby objąć wszystkie B I $S$$3m$ $BI_i$$3*max$$max$$BI_i$$a_i$$L$$BI_i$ (niebieska linia na rysunku).

Następnie skonstruować zaczynając od kopii L , a następnie dodać m grup suma G, J , każdy wykonany z kopią trzech ułożonych odstępach podstawy rozciąga się w taki sposób, że ich piramidy znacznik nie przecinają (patrz linie czerwony + zielony na dole rysunku). Następnie dodać na początku trzech przedziałów bazowych G J piramidy suma z B przedziałów o wzrastającej długości (rozłączne z piramid markera).$T$$L$$m$ $G_j$$G_j$$B$

Załóżmy, że istnieje bijectcja między S i T, która zachowuje włączenie interwału (w jednym kierunku od S do T).

Następnie każdy piramidy znacznik S musi odpowiadać piramidy markerową t (Jedynym sposobem na łańcuch inkluzyjny odstępach), a więc dokładnie trzy przedziały zasad ( B I j 1 , B I j 2 , B I j 3 I) S muszą być przypisane do danej grupy G j . Ponadto, odstępy jednostkowe B I j k musi być odwzorowany na piramidy suma z G j i nie może być „wymieniane” między różnymi grupami.$max$$BI_{j_1},BI_{j_2},BI_{j_3}$$S$$G_j$$BI_{j_k}$$G_j$

W podobny sposób można udowodnić, że jeśli istnieje bijection, to oryginalny problem z pojedynczą 3-partycją ma rozwiązanie.

Przykład redukcji z jednego problemu 3-partycji $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Uwaga: jak zaobserwowano w komentarzach, niebieskie przedziały L w S i T nie są istotne dla zmniejszenia.

$I_i \subseteq I_j$$(I_j \rightarrow I_i)$