Как найти самую длинную возрастающую подпоследовательность среди всех простых путей невзвешенного общего графа?

Question

Пусть G = (V, E) - невзвешенный общий граф, в котором каждая вершина v имеет вес w (v).

Растущая подпоследовательность простого пути p в G - это последовательность вершин p, в которой веса всех вершин вдоль этой последовательности возрастают. Простые пути могут быть закрытыми путями.

Самая длинная возрастающая подпоследовательность (LIS) простого пути p является возрастающей подпоследовательностью p, такой, что имеет максимальное количество вершин.

Вопрос в том, как найти самую длинную возрастающую подпоследовательность среди всех простых путей G?

Обратите внимание, что граф не является ненаправленным, поэтому он не является ориентированным ациклическим графом (DAG).

Answer 1

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

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

1. Сортировка всех узлов по весу,
2. Отбрасывая все, кроме одного узла каждого веса, и
3. Формирование LIS путем последовательного посещения каждого узла.

Это приводит к очень быстрому алгоритму для общей проблемы. За время O(m + n) найдите все подключенные компоненты. Для каждого подключенного компонента используйте предыдущий алгоритм во времени O(Sort(n)), где Sort (n) - время, необходимое для сортировки n элементов (которое может быть Θ(n log n), если вы используете heapsort, Θ(n + U) для сортировки по сегментам, Θ(n lg U) для сортировки по осям и т. Д.). Затем верните самую длинную последовательность, которую вы найдете.

В целом, время выполнения равно O(m + n + &Sort(n)), что превосходит мой предыдущий подход и должно быть намного проще для кодирования.

---

Я первоначально опубликовал этот ответ, который я оставлю, потому что я думаю, что это интересно:

Представьте, что вы выбираете простой путь из графа G и смотрите на самую длинную возрастающую подпоследовательность этого пути. Хотя путь проходит по всему графику и может иметь много промежуточных узлов, самая длинная возрастающая подпоследовательность этого пути действительно заботится только о

• первый узел на пути, который также является частью LIS, и
• с этой точки, следующее по величине значение в пути.

В результате мы можем подумать о формировании ЛИС, подобной этой. Начните с любого узла на графике. Теперь перейдите к любому узлу на графике, который (1) имеет более высокое значение, чем текущий узел, и (2) достижим от текущего узла, затем повторите этот процесс столько раз, сколько необходимо. Цель состоит в том, чтобы получить максимально возможную последовательность возрастающих значений.

Мы можем смоделировать этот процесс как поиск самого длинного пути в DAG. Каждый узел в группе обеспечения доступности баз данных представляет узел в исходном графе G, и существует ребро от узла u к узлу v, если

• есть путь от U до V в G, и
• w(u)

Это DAG из-за этого второго условия, хотя исходный график не является DAG.

Таким образом, мы можем решить эту общую проблему в два этапа. Сначала создайте DAG, описанный выше. Для этого:

1. Найдите связанные компоненты исходного графа G и пометьте каждый узел его номером подключенного компонента. Время: O(m + n).

2. Для каждого узла u в G создайте соответствующий узел u'в новой группе DAG D. Время: O(n).

3. Для каждого узла u в G и для каждого узла v в G, который находится в том же SCC, что и u, если w(u) 2) в худшем случае, Θ(n) в лучшем случае.

4. Найдите самый длинный путь в D. Этот путь соответствует самой длинной возрастающей подпоследовательности любого простого пути в G. Время: O(m + n).

Общее время выполнения: Θ (n²) в худшем случае, Θ(m + n) в лучшем случае.