При фиксированном ориентированный граф (орграф) , то Проблема Решение -раскраска спрашивает , может ли входной Орграф имеет гомоморфизм к . (Гомоморфизм в - это отображение из в , сохраняющее дуги, то есть, если - дуга в , то - это дуга )
Класс задач ЦВЕТА тесно связан с гипотезой дихотомии для CSP, изложенной Федером и Варди (доступно на сайте citeseer ).
В этой статье 2001 года (доступной на странице автора здесь ) Федер доказывает теорему дихотомии, когда - ориентированный цикл (под ориентированным циклом я подразумеваю неориентированный цикл, где каждое ребро заменяется одной дугой, которая может быть ориентирована произвольно) другими словами, он показывает , что для любого ориентированного цикла , -раскраска либо полиномиально разрешимы или NP-полной.
К сожалению, классификация Федера является весьма нетривиальной и не явной, поскольку сложность многих случаев связана со сложностью некоторых ограниченных вариантов SAT, которые зависят от ориентации. Глядя на бумагу, я не смог определить ответ на свой вопрос:
Вопрос: Каков наименьший размер ориентированного цикла , так что -ЦВЕТ является NP-полным?
Ответ может быть сформулирован где-то в литературе, но я не смог его найти.
Редактировать:Позвольте мне дать более подробную информацию о классификации Федера. Фидер показывает, что любой NP-полный ориентированный цикл должен быть сбалансированным, то есть иметь одинаковое количество дуг в обоих направлениях (следовательно, он имеет четный порядок). Затем рассмотрим «уровни», вызванные ориентацией (начните обходить цикл в произвольной вершине; если дуга идет направо, вы поднимаетесь на 1, если дуга налево, вы понижаетесь на 1). Затем, если существует не более одного «движения сверху вниз», оно является полиномиальным. Если существует по крайней мере 3 таких «прогона», и цикл является ядром, он является NP-полным. (В примере Андраса из комментариев есть три таких «прогона», но цикл не является ядром.) Наиболее сложными являются случаи с двумя «прогонами сверху вниз». Некоторые из них сложные, некоторые полиномиальные, и Федер связывает их со специальными задачами SAT для получения дихотомии.
В качестве промежуточного вопроса: Какой наименьший ориентированный цикл имеет три цикла «сверху вниз» и является ядром? Такой пример будет NP-полным к описанному выше обсуждению.
источник
Ответы:
Что касается промежуточного вопроса (ядро с тремя циклами сверху вниз), как насчет этого?
Некоторые обозначения: я буду описывать прогоны словами в{ l , r}* с, например, l l r l соответствующий подграфу ⋅←⋅←⋅→⋅←⋅ , Уровень увеличивается наr дуги и уменьшается на l дуги, и я предполагаю, что его минимум 0 , Некоторые прямые ограничения:
Однако для максимального уровня4 есть решение длины 36 : рассматривать D дано (rrrlrrlllrll)3 , Это имеет требуемый верхний нижний ряд и является ядром (см. Ниже). Из-за вышеуказанных ограничений он обязательно минимален, поскольку каждый прогон имеет только один «обратный» край.
Чтобы убедить себя, что это ядро, давайте сначала назовем вершины (v1,…,v36 ). Дно (то есть уровень0 ) вершины v1,v13,v25 , Любой гомоморфизмφ от D подграф должен сохранять уровни, и в частности φ(v1)∈{v1,v13,v25} ; по модулю очевидного автоморфизмаvi↦vi+12 , достаточно рассмотреть дело φ(v1)=v1 , Рассмотрим окрестностиv1 в D (отмечены уровнями):
Начиная сφ(v1)=v1 , у нас есть φ(v2)∈{v36,v2} , Но еслиφ(v2)=v36 , тогда φ(v3)=v35 и у нас нет возможного значения для φ(v4) , Мы получилиφ(v2)=v2,φ(v3)=v3,φ(v4)=v4 , следующийφ(v5)∈{v3,v5} , но для φ(v5)=v3 мы получили φ(v6)=v4 без возможного значения для φ(v7) , Такφ должно быть личность на всем протяжении v1→…→v7 и повторяя один и тот же аргумент для остальных прогонов, то же самое верно для всех D , В частности,φ не отображается D на правильный подграф.
источник