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

10

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

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

Биекция монотонна WRT порядка включения множества на и T . X Y S , f ( X ) f ( Y )ST

XYS, f(X)f(Y)

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

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

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

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

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

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

a3nm
источник
S I1,I2,...,Inn+1IiIj(IjIi)IiIj1,...,Ijm|Ij1|=|Ij2|=...=|Ijm|(IjkIi)T
2
Интервал может быть включен в несколько несопоставимых интервалов, например, [2, 3] включен в [1, 3] и [2, 4], поэтому я думаю, что ваша древовидная конструкция не даст дерево, а направленный ациклический граф. Я думаю, что проверка того, являются ли два DAG изоморфными (или скорее встраиваемыми в том смысле, о котором я спрашиваю), является NP-сложной задачей.
13
Вы правы, вышеприведенный подход не верен!
Марцио Де Биаси
X,Y,XYf(X)f(Y)
@ MohammadAl-Turkistany: см. Обсуждение в комментариях к ответу Марцио
3

Ответы:

8

Вот попытка доказать, что задача без обратного условия является 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

3mA={a1,a2,...,a3m}BmA1,...,AmAiB

max=ai+3m

S3m BIi3maxmaxBIiaiLBIi (синяя линия на рисунке).

TLm GjGjB

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

maxBIj1,BIj2,BIj3SGjBIjkGj

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

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

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

IiIj(IjIi)

Марцио де Биаси
источник
Да, похоже, это правильно, спасибо большое! (Просто замечание: синие интервалы не нужны, чтобы заставить сокращение работать, я думаю.) Я скоро приму, если не найду оснований сомневаться в том, что это сокращение работает.
a3nm
@ a3nm: да, но я обнаружил это после рисования рисунка :-). Я до сих пор не уверен на 100%, что в сокращении нет скрытых ошибок (более того, второй раз за две недели я нахожу NP-полное доказательство, которое использует унарный 3-секционный ... очень странно :-)
Marzio Де Биаси
Нет, это кажется правильным: ясно, что решение с 3 разделами дает решение интервальной задачи. Теперь, перейдя от проблемы интервалов к 3-секционному: обязательно отображение интервалов отображает красные интервалы в красные интервалы (из-за пирамид маркеров); то же самое количество красных интервалов, поэтому интервал красный, если изображение в соответствии с отображением. Маркеры отображаются в правый красный интервал (потому что иначе это потомок и минимальность). Теперь, если красный отображается на красный, а маркеры отображаются в соответствии с ожиданиями, цифры должны совпадать, поэтому у нас правильный раздел. Я думаю, что это имеет смысл!
13
@ a3nm: я видел, что вы приняли ответ; Как вы думаете, в результате этого достаточно интересно написать совместную работу?
Марцио Де Биаси
Tf