Транзитивная редукция из линейного расширения частичного порядка

Существует ли эффективный алгоритм для создания транзитивного сокращения из одного линейное расширение частичного заказа?

Обновление: На самом деле частичный порядок известен. Мне также известно о временной сложности вычисления транзитивной редукции заданного частичного порядка. . Что я хотел знать, так это: учитывая частичный порядок и одно из его линейных расширений, можно ли уменьшить временную сложность?


algorithm graph-theory partial-ordering
person Martin Krasser    schedule 17.09.2015    source источник
comment
Поскольку может быть общее линейное расширение для нескольких частичных порядков с разными транзитивными редукциями, это невозможно — если предположить, что вы хотите найти транзитивную редукцию частичного порядка, учитывая только одно из его линейных расширений.   -  person G. Bach    schedule 17.09.2015
comment
Более конкретно, как бы вы, как человек, решили проблему, когда (1) скрытый частичный порядок тотален (2) скрытый частичный порядок везде не определен.   -  person David Eisenstat    schedule 17.09.2015
comment
Итак, чтобы избежать путаницы: при заданном входном отношении R вычисление транзитивной редукции может быть выполнено с помощью топологической сортировки? Кроме того, вопрос заключается в том, станет ли задача вычислительно проще, если линейное расширение R задано как часть входных данных?   -  person Codor    schedule 17.09.2015
comment
Да, мой вопрос: становится ли проблема вычислительно проще, если линейное расширение R дополнительно задано как часть ввода? Но вычисление транзитивной редукции R нельзя выполнить с помощью топологической сортировки.   -  person Martin Krasser    schedule 17.09.2015

Ответы (2)


arrow_upward
4
arrow_downward

Говоря асимптотически, ответ — нет. Существует тривиальная нижняя граница Omega(n + m) просто из-за того, что нужно проверять весь ввод, а топологическая сортировка дает линейное расширение во времени O(n + m), что не добавляет асимптотических затрат любому правильному алгоритму.

person David Eisenstat    schedule 17.09.2015

arrow_upward
0
arrow_downward

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

person Codor    schedule 17.09.2015
comment
Транзитивное сокращение частичного порядка не обязательно должно быть линейным порядком, которым является каждый топологический порядок. - person G. Bach; 17.09.2015
comment
Спасибо за комментарий, однако я запутался в понятиях. Топологическая сортировка — это линейное расширение ее входных данных, что является полным порядком, не так ли? - person Codor; 17.09.2015
comment
Это так, но я понимаю вопрос так: ваши входные данные — это линейное расширение некоторого (неизвестного) частичного порядка, а то, что Мартин хочет вычислить, — это транзитивное сокращение частичного порядка. - person G. Bach; 17.09.2015
comment
Итак, вы понимаете вопрос как «данное линейное расширение E некоторого частичного порядка (который не задан явно) P, вычислить транзитивное сокращение P»? - person Codor; 17.09.2015
comment
Да, я так понимаю. Какова ваша интерпретация? - person G. Bach; 17.09.2015
comment
Видимо, моя интерпретация не имела смысла. Я прочитал это как «Учитывая некоторый частичный порядок P, вычислить линейное расширение E и транзитивное сокращение E» (где последний шаг не требуется). - person Codor; 17.09.2015
comment
Я обновил свой вопрос и надеюсь, что он лучше объясняет, что я ищу. - person Martin Krasser; 17.09.2015