Какова сложность этой краевой проблемы окраски?

17

Недавно я столкнулся со следующим вариантом окраски краев.

Для связного неориентированного графа найдите раскраску ребер, которая использует максимальное количество цветов, а также удовлетворяет ограничению, согласно которому для каждой вершины ребра, инцидентные используют не более двух цветов.vv

Мое первое предположение - проблема NP-сложная. Классические NP-трудные доказательства для задач раскраски графов в основном сводятся к 3SAT. Но, на мой взгляд, эти доказательства бесполезны для этой задачи, потому что ребра, падающие на вершину, могут быть окрашены в один и тот же цвет, поэтому мы не можем построить логические компоненты в графе.

Может ли эта проблема быть NP-трудной? Если да, что является доказательством? Если мы не можем найти точное доказательство, есть ли способ определить сложность этой проблемы?

Благодарность!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
источник
Возможно, смешанная или ограниченная в цвете окраска гиперграфа может быть началом? Например, dx.doi.org/10.1016/j.disc.2008.04.019
Саламон,
Кажется, ваша проблема в P, в два этапа: (1) ваша задача эквивалентна поиску подмножества максимального размера ребер, так что каждая вершина имеет степень не более двух, и (2) последняя проблема, кажется, находится в P, скажем, приведение к соответствию. Что касается (1), обратите внимание, что любое решение вашей проблемы с k цветами дает подграф степени 2 размера k (просто оставьте одно ребро от каждого цвета), и наоборот, любой подграф степени 2 размера k дает решение с цветами k (просто закрасьте каждое ребро в подграфе своим собственным цветом, закрасьте остальные ребра любым из цветов). Что мне не хватает?
Нил Янг
Мне жаль, что в вашем ответе есть несколько ошибок. Во-первых, проблема «найти подмножество максимального размера ребер таким образом, чтобы каждая вершина имела степень не более двух», является NP-трудной, редукция до 3SAT (я действительно не знаю, как у нее может быть приведение к сопоставлению). Более того, «любой подграф степени 2 размера k» ​​не дает «решения с k цветами», например, Complete Graph. Все же разрешите поблагодарить вас.
RIC_Eien
Да, ты прав. Что касается (2), то шаг «покрасить остальные ребра любым из цветов» может дать некоторые вершинные ребра трех цветов. Отдельно Марек Чробак предложил мне следующий алгоритм. Я думаю, что это дает 3-приближение: (i) найти максимальное соответствие M; (ii) раскрасить каждое ребро в М своим собственным уникальным цветом; (iii) покрасить оставшиеся края в белый цвет.
Нил Янг
@RIC_Eien: С риском дальнейшего смущения. Вы уверены, что «проблема» в том, чтобы найти подмножество максимальных размеров ребер таким образом, чтобы каждая вершина имела степень не более двух », является NP-трудной»? Учитывая G = (V, E), создайте двудольный G2 = (U, W, E2), где для каждой вершины v в V есть v 'в U и v' 'в W, и E2 = {(u', w ''): (u, w) в E}. Тогда соответствия в G2 соответствуют множествам ребер степени 2 в G, и соответствие сохраняет размер? (Поскольку каждый k-цикл C в G соответствует в G2 либо 2k-циклу (если k нечетно), либо двум k-циклам (если k четно).) Таким образом, максимальное совпадение в G2 решает его. Что я упускаю в этот раз?
Нил Янг

Ответы:

15

Эта проблема является NP-трудной и APX-трудной; см .: Adamaszek and Popa, Результаты аппроксимации и твердости для задачи о максимальном раскрашиванииQ , Конспект лекций по информатике 6507 (2010) 132-143 .

Параметризованные аспекты сложности этой проблемы рассматриваются в этой недавней статье .

VB Le
источник
Я долго думал об этой хорошей проблеме ... Не могли бы вы описать сокращение? У меня нет доступа к бумаге. Благодарность!
user13667
5
@ user13667 Вы можете попросить авторов прислать вам копию их статьи. Я думаю, что они были бы рады сделать это.
vb le
5
Также был изучен связанный с этим вопрос поиска окраски, которая максимизирует количество цветов при минимальном размере самой большой цветовой группы. Например, эта магистерская работа имеет несколько подробных результатов.
Нилдхара