Вопрос о линейных расширениях частичных порядков

Если вам дан набор частичных заказов, топологическая сортировка скажет вам, есть ли расширение коллекции до общего заказа (в данном случае расширение представляет собой общий заказ, соответствующий каждому из частичных заказов).

Я встретил вариант:

Зафиксируем множество . Вам даны последовательности элементов, взятых из без повторений (последовательности имеют длину от 1 до ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

Есть ли способ зафиксировать ориентации для каждой из последовательностей (прямой или обратной), чтобы результирующий набор цепочек (рассматриваемый как частичный порядок) допускал расширение?

Эта проблема хорошо известна?

Примечание: ориентация выбрана для всей последовательности. Так что, если последовательность , вы можете либо сохранить ее таким образом, либо переключить ее на , но вы не можете больше ничего делать. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Суреш Венкат
источник

Если каждая из последовательностей имеет длину

тогда можно думать о каждой последовательности как о ненаправленном ребре, и мы спрашиваем, можно ли ориентировать неориентированный граф как DAG - тогда и только тогда, когда цикла нет. Но жадный алгоритм также работает. Начните с ребра и сориентируйте его произвольно и продолжайте как можно дольше, и если вы застряли, вы знаете, что это невозможно. Вы пробовали это для своего варианта? Похоже, это может работать.

2

$2$

Чандра Чекури

Каждый неориентированный граф может быть ориентирован на DAG. Просто выберите порядок вершин и используйте его для ориентации ребер.

Дэвид Эппштейн

Вы правы, конечно, я не думаю прямо.

Чандра Чекури

В моем варианте каждая подпоследовательность имеет длину ровно 4, поэтому ответ Юрия начинается. Моя единственная надежда на этот момент состоит в том, что подпоследовательности имеют очень особую структуру и связаны друг с другом, поэтому, возможно, что-то конкретное для проблемы поможет. Но нет общего молотка.

Суреш Венкат

Если каждая последовательность имеет длину 3, проблема известна как Между . Даже проблема Межуниверсальности NP-трудна. В этой задаче нам дан набор вершин и множество ограничений вида лежит между и . Наша цель - упорядочить все вершины, чтобы максимизировать количество удовлетворенных ограничений. Опантри [1] доказал, что вариант решения этой проблемы NP-труден. Чор и Судан [2] доказали, что это SNP-hard. $u$ $v$ $w$

Наиболее известный алгоритм приближения для задачи Чора и Судана удовлетворяет 1/2 всех ограничений, если экземпляр полностью выполним.

[1] Дж. Опантри. Проблема полного порядка, SIAM Journal по вычислительной технике , 8 (1): 111—114, февраль 1979 г.

[2] Б. Чор и М. Судан. Геометрический подход к промежуточности , SIAM Journal по дискретной математике, 11 (4): 511-523, ноябрь 1998.

Исправления: уточнено, что решение проблемы является NP-сложным.

Юрий
источник

Юрий, значит ли это, что проблема решения вопроса о том, могут ли быть выполнены все ограничения, также сложна?

Чандра Чекури

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$

Вопрос о линейных расширениях частичных порядков

Ответы: