Разделение ребер на радужные треугольники

9

Мне интересно, если следующая проблема NP-трудна.

Входные данные: G=(V,E) простой график и раскраска f:E{1,2,3} краев (f не проверяет какие-либо конкретные свойства).

Вопрос: возможно ли разбиениеE в |E|/3 треугольники, так что каждый треугольник имеет один край каждого цвета?

Я знаю, что без цветов проблема «разбиения края» графа на Kn, n3NP-трудный (см . NP-Полнота некоторых проблем с краевым разделением ), но с цветами, которые я не знаю.

Я также был бы заинтересован в результате для крайнего разбиения на радугу Kc, с cпостоянная. Конечно, в этом случае проблема становится:

Входные данные: G=(V,E) простой график и раскраска f:E{1,,c(c1)/2} краев (f не проверяет какие-либо конкретные свойства).

Вопрос: возможно ли разбиениеE в |E|/(c(c1)/2) Kcх, такая что каждая клика Kc имеет один край каждого цвета?

user32018
источник

Ответы:

1

Я перешел по ссылке в вопросе, и сокращение там фактически приводит к графам, ребра которых имеют естественную окраску, так что каждый Kn На графике присутствует «радуга» Kn"(имеет ровно одно ребро каждого цвета). Другими словами, мы можем легко отрегулировать уменьшение в этой бумаге так, чтобы оно сводилось к вашей проблеме, а не уменьшалось до разбиения на Kns проблема: просто назначьте каждому ребру цвет в соответствии с этой естественной раскраской, и тогда график можно будет разбить на «радугу» Kns "тогда и только тогда, когда он может быть разбит на Knс на всех.

Базовая структура сокращения в этой статье может быть выполнена с помощью следующих 3 шагов:

  1. Создайте много копий определенного графика Hn,p,
  2. Определите определенные части некоторых копий Hn,p друг с другом (т.е. объединить вершины / ребра между несколькими различными копиями Hn,p).
  3. Удалите определенные вершины / ребра из некоторых копий.

График Hn,p имеет в качестве своих вершин множество длиныn векторы по модулю p для которого компоненты добавляют к 0 модификация p, Ребра соединяют каждые две вершины, которые отличаются только двумя компонентами с разницей+1 а также 1 в этих двух компонентах.

Я предлагаю следующую раскраску для этого графика: назначьте цвет каждому ребру в соответствии с его направлением. Еслиx а также y смежные вершины, то xy вектор с n2 компоненты, равные 0один компонент равен 1 и один компонент равен 1, Другими словами, для каждого края(x,y) есть (n2) варианты для каких компонентов xyненулевые Если мы назначим уникальный цвет для каждой из этих опций, то у нас будет раскраска для всех ребер, так что у каждого ребра в одном и том же направлении будет одинаковый цвет. Довольно легко проверить, что вKn в Hn,pв том же направлении. Поэтому каждыйKn в Hn,p это радуга Kn под эту раскраску.

Когда мы следуем за сокращением, мы используем эту раскраску для каждой копии Hn,p, Поэтому в конце шага 1 в приведенном выше списке каждыйKn на графике радуга Kn,

На шаге 2 приведенного выше списка мы идентифицируем некоторые вершины / ребра друг с другом. В частности, в сокращении мы всегда определяемKn с другим Kn, Но в этой ситуации (где всеKnс из копии Hn,p) каждый Kn это либо перевод "стандарт Kn«который называет газета K или перевод K, Поэтому мы либо идентифицируем две параллельныеKnс или два Knс "сальто" друг от друга. В любом случае, края, которые идентифицированы по двумKns параллельны и поэтому имеют одинаковый цвет. Например, см. Рисунок 2 в документе; идентифицированные ребра всегда параллельны. Таким образом, поскольку мы никогда не пытаемся идентифицировать два ребра разных цветов, раскраска в конце шага 1 в приведенном выше списке может быть естественным образом превращена в раскраску в конце шага 2. Идентификация некоторых вершин / ребер вместе не создает любой новыйKnс, так что в конце этого шага все еще Kn это радуга Kn,

Наконец, в шаге 3 мы удаляем некоторые вершины / ребра, которые также не создают новых Kns. Таким образом, у нас есть желаемое свойство: под цвет, который я указал, каждыйKn на графике, созданном этим сокращением, есть радуга Kn,

Михаил Рудой
источник