Направленные NP-сложные проблемы на DAG

Ширина дерева показывает, насколько близок график к дереву. Несколько NP-трудных задач можно решить на графах с ограниченной шириной дерева. Если проблема остается NP-трудной на деревьях, то ширина дерева не может нас спасти. Это было мотивом одного из моих предыдущих вопросов, в котором задавались проблемы с NP-сложными задачами на деревьях.

Существует несколько направленных версий ширины дерева, измеряющих, насколько близок ориентированный граф к ориентированному ациклическому графу (DAG). Каковы некоторые направленные проблемы, которые остаются несерьезными в DAG? Направленная задача существенно использует направления ребер. Например, гамильтонов путь является направленной задачей, а покрытие вершин - нет. Один из ответов на мой предыдущий вопрос дал общий рецепт для создания проблем, которые трудно на деревьях. Есть ли такой рецепт для ГПДР?

Это только частично отвечает на первый вопрос поста:

Каковы некоторые направленные проблемы, которые остаются несерьезными в DAG?

В [1] дано несколько естественных задач на ориентированных графах, которые остаются NP-трудными на DAG. Мотивация статьи - найти «хорошую» меру ширины для орграфов. Они утверждают, что недостатком многих мер для орграфов является то, что они постоянны для DAG, но многие направленные аналоги естественных проблем остаются NP-трудными для DAG. Подробнее об этом см. Также [2] и ссылки на эти статьи.

[1] Роберт Ганян, Петр Хлинены, Йоахим Кнейс, Александр Лангер, Ян Обджалек, Питер Россманит: О мерах ширины диграфа в параметризованной алгоритмике. IWPEC 2009: 185-197. Полная версия

[2] Роберт Ганян, Петр Хлинени, Йоахим Кнейс, Даниэль Майстер, Ян Обджалек, Питер Россманит, Сомнат Сикдар: Есть ли хорошие меры ширины диграфа? IPEC 2010, чтобы появиться. Arxiv

Известно, что некоторые проблемы маршрутизации являются NP-сложными и даже трудно приближаемыми к полиномиальным факторам в DAG. К ним относятся такие проблемы, как максимальные пути, не пересекающиеся по краям, и минимизация заторов. См. Статьи Эндрюса, Чужоя, Ханны, Чжана и других для получения дополнительной информации.

$\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$$G$$G'$$E(x,y)$$\varphi$$E(x,y)\lor E(y,x)$$G\models\varphi\iff G'\models\varphi'$

Знаменитая проблема ОТКРЫТОГО [8] из списка Гэри и Джонсона выходит за рамки P, но доказано, что она доказана как NP-C. Эта проблема на DAG. В каждом раунде вы можете удалить не более трех вершин, которые не имеют входящего ребра. Решите, можно ли удалить все вершины DAG в K раундах? Открыт с 1970-х годов.