Bijections monotones entre listes d'intervalles

J'ai le problème suivant:

Entrée: deux ensembles d'intervalles et (tous les points d'extrémité sont des entiers). Requête: existe-t-il une bijection monotone ? $S$ $T$
$f:S \to T$

Le bijection est monotones l'ordre wrt d'inclusion ensemble sur et . $S$ $T$

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

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

[Je n'exige pas ici la condition inverse. Mise à jour: si la condition inverse était requise, c'est-à-dire , alors ce serait dans PTIME car cela revient à tester l'isomorphisme des posets d'inclusion correspondants (qui ont ordre dimension 2 par construction), qui se trouve dans PTIME par Möhring, Classes ordonnées calculables d' ensembles ordonnés , Théorème 5.10, p. 61. $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

Le problème est dans : on peut vérifier efficacement si un donné est une bijection monotone. $\mathsf{NP}$ $f$

Existe-t-il un algorithme polynomial pour ce problème? Ou est-ce -hard? $\mathsf{NP}$

La question peut être posée plus généralement comme l'existence d'une bijection monotone entre deux posets donnés de dimension d'ordre 2.

En utilisant une réduction inspirée des réponses à cette question , je sais que le problème est -hard lorsque les dimensions ne sont pas restreintes. Cependant, il n'est pas clair si la réduction fonctionnerait également lorsque les dimensions sont restreintes. $\mathsf{NP}$

Je suis également intéressé de connaître la tractabilité lorsque la dimension est simplement délimitée par une constante arbitraire (pas seulement 2).

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

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$

Un intervalle peut être inclus dans plusieurs intervalles incomparables, par exemple [2, 3] est inclus dans [1, 3] et [2, 4], donc je pense que la construction de votre arbre ne donnera pas un arbre mais un graphique acyclique dirigé. Vérifier si deux DAG sont isomorphes (ou plutôt embarquables dans le sens où je le demande) est NP-difficile en général, je pense.

a3nm

Vous avez raison, l'approche ci-dessus n'est pas correcte!

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: cf la discussion dans les commentaires sur la réponse de Marzio

a3nm

Réponses:

Voici une tentative pour prouver que le problème sans condition inverse est NP-difficile.

$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$ (ligne bleue sur la figure).

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

Supposons qu'il existe une bijection entre S et T qui préserve l'inclusion d'intervalle (dans une direction de S à T).

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

De la même manière, il peut être prouvé que s'il existe une bijection, le problème unaire original à 3 partitions a une solution.

entrez la description de l'image ici $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Remarque: comme observé dans les commentaires, les intervalles bleus L dans S et T ne sont pas essentiels pour la réduction.

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

Marzio De Biasi
la source

Oui, il semble que ce soit correct, merci beaucoup! (Juste une remarque: les intervalles bleus ne sont pas nécessaires pour que la réduction fonctionne, je pense.) J'accepterai bientôt, sauf si je trouve une raison de douter que cette réduction fonctionne.

a3nm

@ a3nm: oui mais je l'ai découvert après avoir dessiné la figure :-). Je ne suis toujours pas sûr à 100% qu'il n'y a pas d'erreurs cachées dans la réduction (de plus, c'est la deuxième fois en deux semaines que je trouve une preuve NP-complète qui utilise unaire 3 partitions ... très étrange :-)

Marzio De Biasi

Non, cela semble juste: clairement une solution à 3 partitions donne une solution au problème d'intervalle. Passons maintenant du problème d'intervalle à la partition à 3: nécessairement une cartographie d'intervalle mappe les intervalles rouges aux intervalles rouges (à cause des pyramides de marqueurs); même nombre d'intervalles rouges donc l'intervalle est rouge si l'image par le mappage est. Les marqueurs sont mappés sur le bon intervalle rouge (car sinon c'est un descendant, et la minimalité). Maintenant, si le rouge est mappé au rouge et que les marqueurs sont mappés comme prévu, les nombres doivent correspondre, nous avons donc une partition correcte. Je pense que cela a du sens!

a3nm

@ a3nm: J'ai vu que vous avez accepté la réponse; Pensez-vous que le résultat est suffisamment intéressant pour écrire un article conjoint?

Marzio De Biasi

T

$T$

f

$f$