Рассмотрим проблему, когда нам задают в качестве входных данных направленный ациклический граф , функцию маркировки из в некоторый набор с полным порядком (например, целые числа) и где нас просят вычислить лексикографически наименьший топологический вид в терминах . Точнее, топологическая сортировка из является перечислением как так, что для всех , когда в G существует путь от v i до v j , то мы должны иметь i < j . Этикетке такого топологического рода является последовательность элементов S получается как л = λ ( v 1 ) , ... , λ ( v н ) . Лексикографический порядок для таких последовательностей (которые имеют длину | V | ) определяется как l < LEX если существует некоторая позицияiтакая, что l i < L l ' i и l j = l ' j для всехj<i. Обратите внимание на тот факт, что каждая метка вSможет быть назначена нескольким вершинам вV(в противном случае проблема тривиальна).
Эту проблему можно сформулировать либо в варианте вычисления («вычислить лексикографически минимальный топологический вид»), либо в варианте решения («это входное слово - минимальный топологический вид?»). У меня вопрос, в чем сложность этой проблемы ? Это в PTIME (или в FP, для варианта вычисления), или это NP-жесткий? Если общая проблема является NP-трудной, меня также интересует версия, в которой набор возможных меток фиксирован заранее (т. Е. Существует только постоянное количество возможных меток).
Примечания:
Вот небольшой пример из реальной жизни, чтобы мотивировать проблему. Мы можем видеть группу доступности базы данных как представляющую задачи проекта (с зависимостью между ними), а метки представляют собой целые числа, представляющие количество дней, которое занимает каждая задача. Чтобы завершить проект, мне потребуется одинаковое количество времени, независимо от того, какой порядок я выберу для задач. Тем не менее, я хотел бы произвести впечатление на моего босса, и для этого я хочу завершить как можно больше заданий как можно быстрее (жадным образом, даже если это означает, что в конце нужно быть очень медленным, потому что остаются более сложные задания). Выбор лексикографически минимального заказа оптимизирует следующий критерий: я хочу выбрать заказ таким образом, чтобы не было другого заказа o ', а количество дней n было бы после дней я бы выполнил больше заданий с порядком o ', чем с порядком o (т. е. если мой начальник смотрит на время n , я получаю лучшее впечатление с помощью o ' ), но для всех m < n я выполнил не меньше заданий с порядок o ′, чем при заказе o .
Чтобы дать некоторое представление о проблеме: я уже знаю из предыдущих ответов, что следующая связанная проблема трудна: «существует ли топологический вид, который достигает следующей последовательности»? Однако тот факт, что здесь я хочу последовательность, которая минимальна для этого лексикографического порядка, похоже, сильно ограничивает возможные топологические порядки, которые могут его достичь (в частности, уменьшение этих ответов больше не работает). Интуитивно понятно, что гораздо меньше ситуаций, когда у нас есть выбор.
Обратите внимание, что, как представляется, есть интересные перефразирования проблем с точки зрения покрытия множеств (при ограничении задачи двунаправленными группами доступности баз данных, то есть с высотой два): учитывая набор множеств, перечислите их в порядке что минимизирует лексикографически последовательность | S 1 | , | S 2 ∖ S 1 | , | S 3 ∖ ( S 1 ∪ S 2 ) | , … , | S n ∖ (, Проблема также может быть перефразирована на неориентированных графах (постепенно расширяйте связанную область графика, следуя порядку, который минимизирует лексикографическую последовательность непокрытых меток). Однако, изза тогочто последовательностьимеетжадничать во все времена по определению лексикографического порядка, я не могу получить сокращение (например, из дерева Штейнера) к работе.
Заранее спасибо за ваши идеи!
Согласно этой ссылке (1), лексикографически первая проблема топологического порядка является NLOG-полной.
источник