Monotone Bijektionen zwischen Intervalllisten

Ich habe folgendes Problem:

Eingabe: zwei Sätze von Intervallen und (alle Endpunkte sind ganze Zahlen). Abfrage: Gibt es eine monotone Bijektion ? $S$ $T$
$f:S \to T$

Die Bijektion ist monotone WRT der Mengeninklusion Reihenfolge auf und . $S$ $T$

\forall X \subseteq Y \in S, f (X) \subseteq f (Y)

$\forall X\subseteq Y \in S, \ f(X) \subseteq f(Y)$

[Ich benötige hier nicht die umgekehrte Bedingung. Update: wenn der umgekehrte Zustand erforderlich war, dh , dann würde das in PTIME sein , weil es auf Isomorphie Abprüfung der entsprechenden Aufnahme posets (welche Beträge Ordnungsdimension 2 durch Konstruktion), die in PTIME von Möhring, Computationally Tractable Classes of Ordered Sets , Theorem 5.10, p. 61. $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

Das Problem liegt in : Wir können effizient prüfen, ob ein gegebenes eine monotone Bijektion ist. $\mathsf{NP}$ $f$

Gibt es einen Polynom-Zeit-Algorithmus für dieses Problem? Oder ist es -hard? $\mathsf{NP}$

Die Frage kann allgemeiner als das Vorhandensein einer monotonen Bijektion zwischen zwei gegebenen Posets der Ordnungsdimension 2 angegeben werden.

Anhand einer Reduktion, die von den Antworten auf diese Frage inspiriert ist , weiß ich, dass das Problem -hart ist, wenn die Abmessungen nicht eingeschränkt sind. Es ist jedoch nicht klar, ob die Reduzierung auch bei eingeschränkten Abmessungen funktionieren würde. $\mathsf{NP}$

Ich bin auch daran interessiert, etwas über die Traktierbarkeit zu erfahren, wenn die Dimension nur durch eine beliebige Konstante (nicht nur 2) begrenzt ist.

cc.complexity-theory ds.algorithms np-hardness partial-order matching a3nm
quelle

S

$S$

I_{1}, I_{2}, . . ., I_{n}

$I_1,I_2,...,I_n$

n + 1

$n+1$

I_{i} \subseteq I_{j}

$I_i \subseteq I_j$

(I_{j} \to I_{i})

$(I_j \rightarrow I_i)$

I_{i} \subseteq I_{j_{1}}, . . ., I_{j_{m}}

$I_i \subseteq I_{j_1},...,I_{j_m}$

| I_{j_{1}} | = | I_{j_{2}} | = . . . = | I_{j_{m}} |

$|I_{j_1}|=|I_{j_2}|=...=|I_{j_m}|$

(I_{j_{k}} \to I_{i})

$(I_{j_k} \rightarrow I_i)$

T

$T$

Ein Intervall kann in mehreren unvergleichlichen Intervallen enthalten sein, zum Beispiel ist [2, 3] in [1, 3] und [2, 4] enthalten, daher denke ich, dass Ihre Baumkonstruktion keinen Baum, sondern einen gerichteten azyklischen Graphen ergibt. Die Überprüfung, ob zwei DAGs isomorph sind (oder eher in dem Sinne eingebettet werden können, nach dem ich frage), ist meiner Meinung nach im Allgemeinen NP-schwer.

a3nm

Sie haben Recht, der obige Ansatz ist nicht korrekt!

Marzio De Biasi

\forall X, Y, X \subseteq Y \Leftrightarrow f (X) \subseteq f (Y)

$\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$

@ MohammadAl-Turkistany:

Siehe

Antworten:

Hier ist ein Versuch zu beweisen, dass das Problem ohne die umgekehrte Bedingung NP-schwer ist.

$S$

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

$T$

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

$3m$ $A = \{a_1,a_2,...,a_{3m}\}$ $B$ $m$ $A_1,...,A_m$ $A_i$ $B$

$max = \sum a_i + 3m$

$S$ $3m$ $BI_i$ $3*max$ $max$ $BI_i$ $a_i$ $L$ $BI_i$ (blaue Linie in der Abbildung).

$T$ $L$ $m$ $G_j$ $G_j$ $B$

Angenommen, zwischen S und T besteht eine Bijektion, die den Intervalleinschluss (in einer Richtung von S nach T) beibehält.

$max$ $BI_{j_1},BI_{j_2},BI_{j_3}$ $S$ $G_j$ $BI_{j_k}$ $G_j$

In ähnlicher Weise kann bewiesen werden, dass das ursprüngliche unäre 3-Partitions-Problem eine Lösung hat, wenn eine Bijektion vorliegt.

Geben Sie hier die Bildbeschreibung ein $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Hinweis: Wie in den Kommentaren beobachtet, sind die blauen Intervalle L in S und T für die Reduktion nicht wesentlich.

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

Marzio De Biasi
quelle

Ja, es scheint richtig zu sein, vielen Dank! (Nur eine Bemerkung: Die blauen Intervalle sind nicht erforderlich, damit die Reduktion funktioniert, denke ich.) Ich werde sie bald akzeptieren, es sei denn, ich finde einen Grund zu bezweifeln, dass diese Reduktion funktioniert.

A3nm

@ a3nm: ja aber ich habe es nach dem zeichnen der figur entdeckt :-). Ich bin mir immer noch nicht 100% sicher, dass es keine versteckten Fehler bei der Reduzierung gibt (außerdem finde ich zum zweiten Mal in zwei Wochen einen NP-vollständigen Beweis, der eine unäre 3-Partition verwendet ... sehr seltsam :-)

Marzio De Biasi

Nein, es scheint richtig zu sein: Eine Lösung für 3-Partitionen liefert eindeutig eine Lösung für das Intervallproblem. Gehen wir nun vom Intervallproblem zur 3-Partition über: Eine Intervallzuordnung ordnet die roten Intervalle notwendigerweise den roten Intervallen zu (aufgrund der Markierungspyramiden). gleiche Anzahl roter Intervalle, daher ist das Intervall rot, wenn das Bild durch die Zuordnung ist. Die Markierungen werden dem rechten roten Intervall zugeordnet (da es sich sonst um einen Nachkommen und eine Minimalität handelt). Wenn nun Rot auf Rot abgebildet wird und die Markierungen wie erwartet zugeordnet werden, müssen die Zahlen übereinstimmen, damit wir eine korrekte Partition haben. Ich denke es macht Sinn!

A3nm

@ a3nm: Ich habe gesehen, dass Sie die Antwort akzeptiert haben; Denken Sie, dass das Ergebnis interessant genug ist, um eine gemeinsame Arbeit zu schreiben?

Marzio De Biasi

T

$T$

f

$f$