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

12

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

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

Шива Кинтали
источник

Ответы:

7

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

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

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

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

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

Серж Гасперс
источник
6

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

Чандра Чекури
источник
1

φ:=C1C2C3[x(C1xC2xC3x)i=1,2,3x,y(¬Cix¬Ciy¬E(x,y))]GGE(x,y)φE(x,y)E(y,x)GφGφ

регулярность
источник
Кажется, что эта проблема не использует направления краев. Я ищу направленные проблемы.
Шива Кинтали
@Shiva: Почему это не соответствует вашим критериям для направленной проблемы?
Андрас Саламон
@ András: раскраска графика заботится о наличии ребра (u, v). Не имеет значения, направлено ли ребро от u к v или от v к u. С другой стороны, гамильтонова траектория использует направления ребер. Можно изменить направления некоторых ребер и преобразовать экземпляр YES в экземпляр NO.
Шива Кинтали
@Shiva: То есть вы хотите свойство, которое выражается формулой, которая не является симметричной (инвариантной при перестановке переменных)?
Андрас Саламон
@ Андрас: Точно.
Шива Кинтали
1

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

Пэн Чжан
источник