Монотонные биекции между списками интервалов

У меня есть следующая проблема:

Вход: два набора интервалов и (все конечные точки являются целыми числами). Вопрос: существует ли монотонная биекция ? $S$ $T$
$f:S \to T$

Биекция монотонна WRT порядка включения множества на и . $S$ $T$

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

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

[Я не требую обратного условия здесь. Обновление: если требовалось обратное условие, т.е. , то это было бы в PTIME , поскольку она составляет изоморфизм тестирования соответствующего включения ч.у.м. (которые имеют размерность порядка 2 по построению), которая находится в PTIME по Мерингу, вычислительно трактуемые классы упорядоченных множеств , теорема 5.10, с. 61. $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

Проблема в : мы можем эффективно проверить, является ли данное монотонной биекцией. $\mathsf{NP}$ $f$

Есть ли алгоритм полиномиального времени для этой проблемы? Или это хард? $\mathsf{NP}$

Вопрос может быть сформулирован более широко как существование монотонной биекции между двумя заданными позами измерения порядка 2.

Использование сокращения вдохновленного ответов на этот вопрос , я знаю , что проблема -трудной , когда размеры не ограничены. Тем не менее, не ясно, будет ли сокращение работать, когда размеры ограничены. $\mathsf{NP}$

Мне также интересно узнать о возможности тяготения, когда размерность ограничена какой-либо произвольной константой (а не только 2).

cc.complexity-theory ds.algorithms np-hardness partial-order matching a3nm
источник

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$

Интервал может быть включен в несколько несопоставимых интервалов, например, [2, 3] включен в [1, 3] и [2, 4], поэтому я думаю, что ваша древовидная конструкция не даст дерево, а направленный ациклический граф. Я думаю, что проверка того, являются ли два DAG изоморфными (или скорее встраиваемыми в том смысле, о котором я спрашиваю), является NP-сложной задачей.

Вы правы, вышеприведенный подход не верен!

Марцио Де Биаси

\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: см. Обсуждение в комментариях к ответу Марцио

Ответы:

Вот попытка доказать, что задача без обратного условия является NP-трудной.

$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$ (синяя линия на рисунке).

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

Предположим, что существует биекция между S и T, которая сохраняет интервал включения (в одном направлении от S до T).

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

Аналогичным образом можно доказать, что если существует биекция, то исходная унарная задача о 3-разбиениях имеет решение.

введите описание изображения здесь $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Примечание: как отмечено в комментариях, синие интервалы L в S и T не являются существенными для сокращения.

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

Марцио де Биаси
источник

Да, похоже, это правильно, спасибо большое! (Просто замечание: синие интервалы не нужны, чтобы заставить сокращение работать, я думаю.) Я скоро приму, если не найду оснований сомневаться в том, что это сокращение работает.

a3nm

@ a3nm: да, но я обнаружил это после рисования рисунка :-). Я до сих пор не уверен на 100%, что в сокращении нет скрытых ошибок (более того, второй раз за две недели я нахожу NP-полное доказательство, которое использует унарный 3-секционный ... очень странно :-)

Marzio Де Биаси

Нет, это кажется правильным: ясно, что решение с 3 разделами дает решение интервальной задачи. Теперь, перейдя от проблемы интервалов к 3-секционному: обязательно отображение интервалов отображает красные интервалы в красные интервалы (из-за пирамид маркеров); то же самое количество красных интервалов, поэтому интервал красный, если изображение в соответствии с отображением. Маркеры отображаются в правый красный интервал (потому что иначе это потомок и минимальность). Теперь, если красный отображается на красный, а маркеры отображаются в соответствии с ожиданиями, цифры должны совпадать, поэтому у нас правильный раздел. Я думаю, что это имеет смысл!

@ a3nm: я видел, что вы приняли ответ; Как вы думаете, в результате этого достаточно интересно написать совместную работу?

Марцио Де Биаси

T

$T$

f

$f$