Введение
В теории графов и теоретической информатике задача о монохроматическом треугольнике — это алгоритмическая задача на графах, в которой требуется разделить рёбра заданного графа на два подграфа, не содержащих треугольников. Она является NP-полной, но разрешима за фиксированное время на графах с ограниченной шириной дерева.
in which the goal is to partition the edges of a given graph into two triangle free subgraphs. It is NP complete but fixed parameter tractable on graphs of bounded treewidth.
Заявление о проблеме
Проблема монохромного треугольника на вход принимает неориентированный граф G(V,E) с n вершинами, где V – множество вершин, а E – множество ребер.
На выходе – булево значение: true, если множество ребер E графа G можно разбить на два непересекающихся множества E1 и E2, так что оба подграфа G1(V,E1) и G2(V,E2) не содержат треугольников, и false в противном случае. Эта задача принятия решений является NP-полной.
The output is a Boolean value, true if the edge set E of G can be partitioned into two disjoint sets E1 and E2, such that both of the two subgraphs G1(V,E1) and G2(V,E2) are triangle free graphs, and false otherwise. This decision problem is NP complete.
Обобщение на несколько цветов
Проблема может быть обобщена до задачи раскраски рёбер графа без треугольников, заключающейся в нахождении назначения цветов рёбрам графа так, чтобы не существовало треугольника, все рёбра которого окрашены в один и тот же цвет. Задача о монохромном треугольнике является частным случаем раскраски рёбер графа без треугольников, когда в распоряжении имеется ровно два цвета. Если существует раскраска рёбер графа без треугольников двумя цветами, то рёбра каждого цвета образуют два множества E1 и E2 в задаче о монохромном треугольнике. И наоборот, если задача о монохромном треугольнике имеет решение, мы можем использовать один цвет для E1 и второй цвет для E2, чтобы получить раскраску рёбер графа без треугольников.
Связь с теоремой Рэмси
По теореме Рамзи, для любого конечного числа k цветов существует такое число n, что полные графы с n или более вершинами не допускают раскраску рёбер в k цветов без монохромных треугольников. Для k = 2 соответствующее значение n равно 6. То есть, ответ на вопрос о существовании монохромного треугольника в полном графе K6 отрицательный.
Параметризированная сложность
Выразить задачу о монохроматическом треугольнике в монадической логике второго порядка графов (MSO2) можно с помощью логической формулы, утверждающей существование разбиения ребер на два подмножества, такого что не существует трех попарно смежных вершин, все ребра которых принадлежат одному и тому же подмножеству. Из теоремы Курсельэ следует, что задача о монохроматическом треугольнике является параметрически разрешимой для графов с ограниченной шириной дерева. Более точно, существует алгоритм решения этой задачи, время работы которого пропорционально количеству вершин входного графа, умноженному на быстро растущую, но вычислимую функцию ширины дерева.