Сложность гомоморфизма орграфа в ориентированный цикл

9

При фиксированном ориентированный граф (орграф) , то Проблема Решение -раскраска спрашивает , может ли входной Орграф имеет гомоморфизм к . (Гомоморфизм в - это отображение из в , сохраняющее дуги, то есть, если - дуга в , то - это дуга )DDгDгDfV(G)V(D)uvGf(u)f(v)D

Класс задач ЦВЕТА тесно связан с гипотезой дихотомии для CSP, изложенной Федером и Варди (доступно на сайте citeseer ).D

В этой статье 2001 года (доступной на странице автора здесь ) Федер доказывает теорему дихотомии, когда - ориентированный цикл (под ориентированным циклом я подразумеваю неориентированный цикл, где каждое ребро заменяется одной дугой, которая может быть ориентирована произвольно) другими словами, он показывает , что для любого ориентированного цикла , -раскраска либо полиномиально разрешимы или NP-полной.DDD

К сожалению, классификация Федера является весьма нетривиальной и не явной, поскольку сложность многих случаев связана со сложностью некоторых ограниченных вариантов SAT, которые зависят от ориентации. Глядя на бумагу, я не смог определить ответ на свой вопрос:

Вопрос: Каков наименьший размер ориентированного цикла , так что -ЦВЕТ является NP-полным?DD

Ответ может быть сформулирован где-то в литературе, но я не смог его найти.


Редактировать:Позвольте мне дать более подробную информацию о классификации Федера. Фидер показывает, что любой NP-полный ориентированный цикл должен быть сбалансированным, то есть иметь одинаковое количество дуг в обоих направлениях (следовательно, он имеет четный порядок). Затем рассмотрим «уровни», вызванные ориентацией (начните обходить цикл в произвольной вершине; если дуга идет направо, вы поднимаетесь на 1, если дуга налево, вы понижаетесь на 1). Затем, если существует не более одного «движения сверху вниз», оно является полиномиальным. Если существует по крайней мере 3 таких «прогона», и цикл является ядром, он является NP-полным. (В примере Андраса из комментариев есть три таких «прогона», но цикл не является ядром.) Наиболее сложными являются случаи с двумя «прогонами сверху вниз». Некоторые из них сложные, некоторые полиномиальные, и Федер связывает их со специальными задачами SAT для получения дихотомии.

В качестве промежуточного вопроса: Какой наименьший ориентированный цикл имеет три цикла «сверху вниз» и является ядром? Такой пример будет NP-полным к описанному выше обсуждению.

Флоран Фуко
источник
Я не помню быстрого ответа в литературе (возможно, Барнаби Мартин или Флорент Мадлен знали бы). Тем не менее, размер составляет не более 6 вершин и 6 направленных ребер, поскольку можно уменьшить раскраску до раскраски для шести-вершинного орграфа путем замены каждого неориентированного ребра в графах двумя дугами, указывающими на новую вершину между его конечные точки. K3DD
Андрас Саламон
Спасибо Андрас. Тем не менее, я думаю, что ответ должен быть больше, потому что ядром этого примера является просто орграф с уникальной дугой, которая разрешима за полиномиальное время ...
Флоран Фуко
Вы правы, предложенная мной конструкция слишком проста.
Андрас Саламон
Я спросил Флорента Мадлен и Барнаби Мартина, но они не знают ответа напрямую, хотя они, кажется, заинтересованы :-) Мой коллега спросил Федера по электронной почте на прошлой неделе, но он не ответил (пока).
Флоран Фуко
Вторым моим импульсом было использование жесткой версии треугольника. Однако с помощью устройства жесткости от Chvátal et al. (JCT 1971) тогда жесткому треугольнику требуется количество вершин, равное по меньшей мере 9v + 36, если входной граф имеет v вершин, и неясно, как модифицировать эти гаджеты в путях. Возможно, вместо этого можно было бы использовать жесткую направленную траекторию для замены каждого ребра, но мне не ясно, как это сделать, сохранив при этом возможность сопоставить любое ребро графа любому ребру треугольника (но нигде больше), поскольку Очевидный способ сделать это - потребовать симметрию.
Андрас Саламон

Ответы:

5

Что касается промежуточного вопроса (ядро с тремя циклами сверху вниз), как насчет этого?

Некоторые обозначения: я буду описывать прогоны словами в {l,r}с, например, llrl соответствующий подграфу , Уровень увеличивается наr дуги и уменьшается на l дуги, и я предполагаю, что его минимум 0, Некоторые прямые ограничения:

  • Не может быть пробега, состоящего только из lс или только из rс, потому что в противном случае существует очевидный гомоморфизм из D к этому запуску (отображение каждого узла Dк тому же уровню). Это также подразумевает, что максимальный уровень должен быть как минимум3,
  • Если максимальный уровень был 3тогда все прогоны сверху вниз (соответственно снизу вверх) будут иметь вид llr(lr)ill (Соотв. rrl(rl)irr); опять же, не очень трудно найти гомоморфизм изD на ходу, который сводит к минимуму i,

Однако для максимального уровня 4 есть решение длины 36: рассматривать D дано (rrrlrrlllrll)3, Это имеет требуемый верхний нижний ряд и является ядром (см. Ниже). Из-за вышеуказанных ограничений он обязательно минимален, поскольку каждый прогон имеет только один «обратный» край.

Чтобы убедить себя, что это ядро, давайте сначала назовем вершины (v1,,v36). Дно (то есть уровень0) вершины v1,v13,v25, Любой гомоморфизмφ от D подграф должен сохранять уровни, и в частности φ(v1){v1,v13,v25}; по модулю очевидного автоморфизмаvivi+12, достаточно рассмотреть дело φ(v1)=v1, Рассмотрим окрестностиv1 в D (отмечены уровнями):

v34(1)v35(2)v36(1)v1(0)v2(1)v3(2)v4(3)v5(2)v6(3)v7(4)

Начиная с φ(v1)=v1, у нас есть φ(v2){v36,v2}, Но еслиφ(v2)=v36, тогда φ(v3)=v35и у нас нет возможного значения для φ(v4), Мы получилиφ(v2)=v2,φ(v3)=v3,φ(v4)=v4, следующийφ(v5){v3,v5}, но для φ(v5)=v3 мы получили φ(v6)=v4без возможного значения для φ(v7), Такφ должно быть личность на всем протяжении v1v7и повторяя один и тот же аргумент для остальных прогонов, то же самое верно для всех D, В частности,φ не отображается D на правильный подграф.

Клаус Дрегер
источник
3
Этот же анализ показывает, что все сбалансированные ориентированные циклы с двумя циклами, которые являются ядрами, имеют длину не менее 24, верно? Таким образом, это дает нижнюю оценку ответа на основную проблему.
Дэвид Эппштейн
Да, хорошая мысль.
Клаус Дрегер
1
Отлично, спасибо, это очень полезно! Можем ли мы убедить себя в том, что это ядро? (обратите внимание, что существует алгоритм полиномиального времени, чтобы проверить, является ли ориентированный циклD это ядро: создать набор |V(D)| ориентированные подпути {Da такой, что a это дуга D}, а затем проверьте, если Dкарты на любой из этих путей; это можно сделать в разное время, см. Гутьяр и др.: sciencedirect.com/science/article/pii/0166218X9290294K )
Флоран Фуко,
1
@FlorentFoucaud Я добавил немного, показывая, что Dэто ядро.
Клаус Дрегер