DAG & Graph: простой путь от s до t, который проходит через как можно больше цветных вершин

Question

У меня есть две отдельные проблемы: они вращаются вокруг графов и определяют подход к поиску простого пути от s до t , который проходит через как можно больше синих вершин.Дополнительно я должен определить, какая из двух проблем является NP-Hard.

Граф в первой задаче является неориентированным графом, где некоторые из вершин синего цвета, а граф в другой задаче является ориентированным ациклическим графом, где некоторые вершины синего цвета.

У меня есть подсказка, что вторую проблему с ориентированным ациклическим графом можно решить с помощью динамического программирования, но мне очень трудно понять, как эту проблему можно смоделировать как проблему динамического программирования, так как яне совсем вижу перекрытие подзадач.Может быть, можно продемонстрировать или уточнить, как это можно сделать?

Также первая проблема должна быть NPHard, которая может быть сведена к гамильтоновой траектории, я могу частично увидеть, как это правильно, но тогда возникает вопрос, может ли вторая проблема с ориентированным ациклическим графом тогдатакже будет сокращен до гамильтонова пути, также делая его NPHard?Почему или почему нет?

Answer 1

Фундаментальная асимметрия NP-завершенности заключается в том, что NP-проблемы всегда можно свести к NP-завершенным или сложным, но NP-завершенные не всегда можно свести к NP-задачам.

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

Что касается второй, представьте, что вы не слышали, как термин «топологическая сортировка» всплывает наветерок ...