Лексикографически минимальный топологический вид помеченного DAG

13

Рассмотрим проблему, когда нам задают в качестве входных данных направленный ациклический граф G=(V,E) , функцию маркировки λ из V в некоторый набор L с полным порядком <L (например, целые числа) и где нас просят вычислить лексикографически наименьший топологический вид G в терминах λ . Точнее, топологическая сортировка из G является перечислением V как v=v1,,vnтак, что для всех , когда в G существует путь от v i до v j , то мы должны иметь i < j . Этикетке такого топологического рода является последовательность элементов S получается как л = λ ( v 1 ) , ... , λ ( v н ) . Лексикографический порядок для таких последовательностей (которые имеют длину | V | ) определяется как l < LEXijvivjGi<jSl=λ(v1),,λ(vn)|V| если существует некоторая позицияiтакая, что l i < L l ' i и l j = l ' j для всехj<i. Обратите внимание на тот факт, что каждая метка вSможет быть назначена нескольким вершинам вV(в противном случае проблема тривиальна).l<LEXlili<Llilj=ljj<iSV

Эту проблему можно сформулировать либо в варианте вычисления («вычислить лексикографически минимальный топологический вид»), либо в варианте решения («это входное слово - минимальный топологический вид?»). У меня вопрос, в чем сложность этой проблемы ? Это в PTIME (или в FP, для варианта вычисления), или это NP-жесткий? Если общая проблема является NP-трудной, меня также интересует версия, в которой набор возможных меток фиксирован заранее (т. Е. Существует только постоянное количество возможных меток).S

Примечания:

Вот небольшой пример из реальной жизни, чтобы мотивировать проблему. Мы можем видеть группу доступности базы данных как представляющую задачи проекта (с зависимостью между ними), а метки представляют собой целые числа, представляющие количество дней, которое занимает каждая задача. Чтобы завершить проект, мне потребуется одинаковое количество времени, независимо от того, какой порядок я выберу для задач. Тем не менее, я хотел бы произвести впечатление на моего босса, и для этого я хочу завершить как можно больше заданий как можно быстрее (жадным образом, даже если это означает, что в конце нужно быть очень медленным, потому что остаются более сложные задания). Выбор лексикографически минимального заказа оптимизирует следующий критерий: я хочу выбрать заказ таким образом, чтобы не было другого заказа o ', а количество дней n было бы послеoon дней я бы выполнил больше заданий с порядком o ', чем с порядком o (т. е. если мой начальник смотрит на время n , я получаю лучшее впечатление с помощью o ' ), но для всех m < n я выполнил не меньше заданий с порядок o ′, чем при заказе o .noonom<noo

Чтобы дать некоторое представление о проблеме: я уже знаю из предыдущих ответов, что следующая связанная проблема трудна: «существует ли топологический вид, который достигает следующей последовательности»? Однако тот факт, что здесь я хочу последовательность, которая минимальна для этого лексикографического порядка, похоже, сильно ограничивает возможные топологические порядки, которые могут его достичь (в частности, уменьшение этих ответов больше не работает). Интуитивно понятно, что гораздо меньше ситуаций, когда у нас есть выбор.

Обратите внимание, что, как представляется, есть интересные перефразирования проблем с точки зрения покрытия множеств (при ограничении задачи двунаправленными группами доступности баз данных, то есть с высотой два): учитывая набор множеств, перечислите их в порядке что минимизирует лексикографически последовательность | S 1 | , | S 2S 1 | , | S 3( S 1S 2 ) | , , | S n(S1,,Sn|S1||S2S1||S3(S1S2)|, Проблема также может быть перефразирована на неориентированных графах (постепенно расширяйте связанную область графика, следуя порядку, который минимизирует лексикографическую последовательность непокрытых меток). Однако, изза тогочто последовательностьимеетжадничать во все времена по определению лексикографического порядка, я не могу получить сокращение (например, из дерева Штейнера) к работе.|Sn(S1Sn1)|

Заранее спасибо за ваши идеи!

a3nm
источник

Ответы:

12

Если разрешено несколько копий одной и той же метки, проблема NP-сложная, за счет сокращения кликов на графиках. Для данного графа в котором вы хотите найти k -клику, создайте DAG с исходной вершиной для каждой вершины G , стоковой вершиной для каждого ребра G и направленным ребром x y всякий раз, когда x является вершиной G это формирует конечную точку ребра у . Дайте вершинам G значение метки 1, а ребрам G - значение метки 0 .GkGGxyxGyG1G0

Тогда в G существует клик тогда и только тогда, когда лексикографически первый топологический порядок образует последовательность из k 1 и ( kkGk 1 0'с, сI-10' ы послеIй1. Например, клика из шести вершин будет представлена ​​последовательностью110100100010000100000. Это лексикографически наименьшая последовательность, которая могла бы начать топологическое упорядочение помеченного DAG, заданного этой конструкцией (замена любого из1на0дала бы последовательность с большим количеством ребер, чем можно было бы найти в простом графе с этим много вершин), и это может быть только началом топологического упорядочения, когдаGсодержит желаемую клику.(k2) 0i1 0i111010010001000010000010G

Дэвид Эппштейн
источник
О, я не думал о кликах. Это хорошее сокращение, спасибо большое! Таким образом, это показывает, что проблема вычисления является NP-сложной, даже с фиксированным алфавитом метки ). Это также подразумевает, что проблема решения «является лексикографически наименьшей последовательностью, меньшей этой», также является NP-сложной (ее можно использовать для вычисления минимума с помощью бинарного поиска). Единственный дополнительный вопрос, который я вижу, заключается в том, является ли проблема «является ли эта точная входная последовательность минимальной» трудной для NP. (С его помощью вы не можете легко проверить, начинается ли минимальное слово с префикса.) Есть ли у вас идеи для этого? {0,1}
a3nm
1
Я подозреваю, что проблема «в том, что эта точная последовательность достижима», является NP-полной, но у меня нет сокращения под рукой. «Является ли эта точная последовательность минимальной» должна быть на втором уровне полиномиальной иерархии, поскольку она требует сочетания экзистенциального количественного определения (достижимо ли) и универсального количественного определения (все достижимые последовательности хотя бы настолько большие).
Дэвид Эппштейн
На самом деле, я уже знаю, что проверка того, достижима ли точная последовательность, является NP-сложной (на алфавите с 3 метками) путем сокращения от унарного 3-разбиения Марцио де Биаси, набросанного здесь: cstheory.stackexchange.com/a/19415 . Но я думаю, что это не говорит о статусе проблемы «является ли это минимально достижимой последовательностью»: когда задается вопрос о том, достижима ли определенная последовательность, в целом у нее будет мало шансов быть минимальной в некотором лексикографическом порядке. В любом случае, то, что показывает ваше сокращение, все еще очень интересно, еще раз спасибо! :)
a3nm
2

Согласно этой ссылке (1), лексикографически первая проблема топологического порядка является NLOG-полной.

λ(u)λ(v)uv

  1. Шоудай, Такаёси. « Лексикографически первая проблема топологического порядка является NLOG-полной ». Письма по обработке информации 33.3 (1989): 121-124.
mhum
источник
4
NLOG-complete - это подмножество полиномиального времени, и (в соответствии с предложением «Обратите внимание» в первом абзаце задачи) выделение меток вершин делает задачу легко решаемой с помощью жадного алгоритма за полиномиальное время. Реальный вопрос в том, что происходит, когда метки не различимы.
Дэвид Эппштейн
Это справедливо. Теперь из вашего ответа ясно, что повторение меток делает проблему более сложной, чем в случае уникальных меток.
Чт