Сложность топологической сортировки с ограниченными позициями

15

Мне дают в качестве входных данных DAG из n вершин, где каждая вершина x дополнительно помечена некоторым S ( x ) { 1 , , nGnx .S(x){1,,n}

Топологическим видом является биекция f из вершин G в { 1 , , n } такая, что для всех x , y , если в G есть путь от x до y, то f ( x ) f ( y ) . Я хочу решить, существует ли топологический вид G такой, что для всех x , f ( x ) S ( xGfG{1,,n}xyxyGf(x)f(y)Gx .f(x)S(x)

Какова сложность этого решения проблемы?

[Примечания: ясно, что это в NP. Если вы посмотрите на график разрешенных пар вершин / позиций с ненаправленными ребрами между парами, которые конфликтуют из-за того, что они нарушают порядок, вы получите график непересекающихся клик, где вы хотите выбрать не более одной пары на клик, не более одной пары на положение и не более одной пары на вершину - похоже, это связано с 3-мерным сопоставлением, но я не могу понять, сложно ли еще с дополнительной структурой этой конкретной задачи.]

a3nm
источник

Ответы:

9

Я думаю, что эта проблема NP-сложная. Я пытаюсь набросать сокращение от MinSAT. В задаче MinSAT нам дают CNF, и наша цель - минимизировать количество удовлетворенных предложений. Эта проблема NP-сложная, см., Например, http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Разделите вершины на две группы - одни будут представлять литералы, другие - клозами, поэтому где v - количество переменных в CNF (обычно обозначается n ), а c - количество предложений. Направьте ребро от каждой литеральной вершины до вершины предложения, где это происходит. Определите S для литеральной вершины, которая представляет x i как { i , i + v + k } (где k - произвольный параметр), поэтому либо f ( x in=2v+cvncSxi{i,i+v+k}k и е ( ˉ х я ) = я + v + K или F ( ˉ х я ) = я и е ( х я ) = я + v + K . Для каждого выражения-вершины пусть S = { v + 1 , , v + k , 2 v + k + 1 , f(xi)=if(x¯i)=i+v+kf(x¯i)=if(xi)=i+v+k , так что k вершин-предложений являются `` маленькими ''.S={v+1,,v+k,2v+k+1,,n}k

Теперь у CNF есть назначение, где по крайней мере предложений ложны тогда и только тогда, когда ваша проблема может быть решена для вышеупомянутого примера. Задача MinSAT состоит именно в том, чтобы проверить, есть ли в формуле CNF φ присвоение, которое делает как минимум k предложений ложными, поэтому это показывает, что ваша проблема является NP-сложной.kφk

Чтобы помочь вам понять это сокращение, вот интуиция: маленькие метки ( ) соответствуют значению истины False, а большие метки ( v + k + 1 , , 2 v + k ) соответствуют Правда. Ограничения для буквальных-вершин , чтобы каждый х я является истинным или ложным , и что ¯ х я1,2,,v+kv+К+1,...,2v+КИксяИкся¯имеет противоположное значение истины. Ребра гарантируют, что если любой литерал имеет значение True, то всем вершинам-предложениям, содержащим его, также присваивается значение True. (В отличие от этого, если всем литералам в предложении присваивается значение False, тогда эта структура графа позволяет назначать вершина-предложение False или True.) Наконец, выбор гарантирует, что k вершин-предложений будет присвоено значение False и c - k из них назначены True. Таким образом, если существует верный топологический вид этого графа, то существует присваивание переменным, которое составляет не менее k из пунктов φККс-ККφfalse (все вершины-предложения, которые были назначены False, плюс, возможно, некоторые из тех, которые были назначены True). И наоборот, если есть присваивание переменным, которое делает по крайней мере из пунктов φ ложным, то существует правильный топологический вид этого графа (мы заполняем метки для буквальных вершин очевидным образом; и для Каждое предложение в φ, которое является истинным, мы присваиваем его соответствующей вершине-предложению метку, которая соответствует Истине; другие вершины-предложения могут получать метки, соответствующие произвольному значению истинности).Кφφ

domotorp
источник
Спасибо за Ваш ответ! Я пытаюсь понять твой эскиз. Не могли бы вы объяснить, что такое ? К
a3nm
1
@ a3nm: k - это параметр, который задается для входа MinSAT.
domotorp
1
@Marzio: SAT не эквивалентно MinSAT с Как и в последней задаче, мы бы требовали, чтобы все пункты были ложными. Ваш ϕ не имеет ложного назначения из всех пунктов. Конечно, это не доказывает, что мое сокращение является правильным ...Кзнак равно|с|φ
Domotorp
Это великолепное сокращение! @ a3nm, я предложил изменить ответ, чтобы объяснить элегантное сокращение domotorp более подробно; Если оно будет одобрено, надеюсь, оно поможет вам лучше понять идеи.
DW
@domotorp: вы правы, я полностью пропустил, что такое MinSAT. Хорошее сокращение !!!
Марцио Де Биаси
2

Обратите внимание, что если вы ослабите проблему, позволив быть произвольным (не обязательно биективным), то он становится полиномиальным. Алгоритм работает аналогично топологической сортировке: вы нумеруете вершины одну за другой, сохраняя множество U ненумерованных вершин, чьи соседние элементы были пронумерованы. По возможности вы выбираете вершину x U и нумеруете ее с наименьшим элементом в S ( x ), который больше, чем номера ее соседей. Нетрудно видеть, что экземпляр ( G , S ) имеет решение, если предыдущий алгоритм работал ( G ,еUИксUS(Икс)(грамм,S) заканчивается всеми пронумерованными вершинами.(грамм,S)

Super0
источник
Справедливо, это ослабление означает, что работает жадная эвристика, и это даже в случае, когда - это не число вершин, а произвольное значение. Согласны ли мы с тем, что в последнем случае, когда приемистость и субъективность больше не эквивалентны, вам нужно ослабить оба (а не только один), чтобы жадная эвристика работала? N
a3nm
2

Тривиальное наблюдение состоит в том, что если для всех x , то эта задача разрешима за полиномиальное время путем сокращения до 2SAT.|S(Икс)|2Икс

Вот как. Введем переменную для каждой вершины x и каждой i такой, что i S ( x ) . Для каждой пары вершин x , y , если существует путь от x до y , мы получаем некоторые ограничения: если i S ( x ) , j S ( y ) и i > j , то мы получаем ограничение ¬ V X , яvИкс,яИксяяS(Икс)Икс,YИксYяS(Икс)JS(Y)я>J . Биективность дает нам другой набор ограничений: для каждой пары x , y вершин с x y , если i S ( x ) и i S ( y ) , мы добавляем ¬ v x , i¬ v y , i . Наконец, требование, чтобы каждой вершине была присвоена метка, дает нам еще один набор ограничений: для каждого x , если S¬vИкс,я¬vY,JИкс,YИксYяS(Икс)яS(Y)¬vИкс,я¬vY,яИкс , мы получаем ограничение v x , iv x , j . (Обратите внимание, что только последний набор ограничений использует обещание, что | S ( x ) |2 для каждого x .)S(Икс)знак равно{я,J}vИкс,яvИкс,J|S(Икс)|2Икс

Я понимаю, что это наблюдение не поможет вам в вашей конкретной ситуации. Прости за это.

DW
источник