3-Clique Partition для графиков фиксированного диаметра

11

Проблема разбиения с 3-мя кликами - это проблема определения , можно ли разбить вершины графа, скажем, , на 3 клики. Эта проблема является NP-трудной из-за простого сокращения проблемы 3-окрашиваемости. Нетрудно видеть, что ответ на эту проблему прост, когда diam ( G ) = 1 или diam ( G ) > 5 . Проблема остается NP-трудной, когда diam ( G ) = 2 простым сокращением от себя (для графа G добавьте вершину и соедините ее со всеми остальными вершинами).Gdiam(G)=1diam(G)>5diam(G)=2G

Какова сложность этой задачи для графов с при 3 p 5 ?diam(G)=p3p5

Бабак Бехсаз
источник

Ответы:

6

Проблема , кажется, в .P

Возьмем две вершины , v с расстоянием ровно 3 (такая пара должна существовать при p 3 ). Они должны иметь разные цвета (я буду использовать R, G, B, чтобы обозначить 3 цвета, а вершины в одной и той же клике окрашены в один и тот же цвет). Wlog предполагает, что у вас красный цвет, а v - зеленый.uvp3uv

Γ(u)uΓ(v)VΓ(u)Γ(v)uvuvvдолжен быть зеленого или синего цвета. Каждая вершина теперь имеет не более двух вариантов выбора, поэтому задача становится экземпляром 2-SAT, который мы можем решить за полиномиальное время.

Ронг Гэ
источник
1
Можете ли вы описать соответствующую формулировку 2-SAT?
user5153
1
B(v)vuv(B(v)B(u))(B(v)¯B(u)¯)
Бабак Бехсаз