Как трудно эта проблема графика?

Вариант решения задачи NP-Complete для общих графов: http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf и не применим. только для треугольников.

Конечно, это все еще не помогает решить вопрос о поисковой версии 3-раскрашиваемых графов и свободе треугольников (вариант решения тривиально находится в P).

МОЙ ОТВЕТ НЕПРАВИЛЬНЫЙ

Я оставлю его для обсуждения. Пожалуйста, не голосуйте против, идея все еще может быть полезна.

Я собираюсь утверждать, что это NP-сложно, основываясь на утверждении, что раскрашивание 3-раскрашиваемого графа в 4 цвета является NP-трудным ( О сложности 4-раскраски 3-раскрашиваемого графа ).

Мы приводим новое доказательство, показывающее, что раскрасить трехкратный граф, используя всего четыре цвета, NP-сложно. Этот результат уже известен, но наше доказательство является новым, поскольку [...]

Предположим, мы можем разбить 3-раскрашиваемый граф на 2 множества A, B, так что ни один из них не имеет треугольника, за полиномиальное время. Затем мы можем решить 4-раскраску следующим образом:

• задать цвет A с помощью C1, C2 и установить B с помощью C3, C4.
• каждый набор может быть 2-раскрашен, так как у него нет треугольника <- ЭТО ГДЕ Я ПОЛУЧИЛ НЕПРАВИЛЬНО
• 2-раскраска 2-раскрашиваемого графа полиномиальна
• мы тогда 4-раскрасили 3 -раскрашиваемый граф за полиномиальное время

Благодаря этой редукции я утверждаю, что то, что вы делаете, должно быть NP-трудным.

Это невозможно для любого набора с 5 тесно связанными узлами, и я могу доказать это с помощью простого мысленного эксперимента. 5 тесно связанных между собой узлов очень распространены в социальных сетях; Беглый взгляд на мой профиль в Facebook, найденный среди членов моей семьи и одного из группы коллег.

Под «тесно взаимосвязанным графом» я подразумеваю набор узлов, в которых узлы связаны с каждым другим узлом. 5 таких узлов выглядят как звезда в пятиугольнике.

Начнем с пяти кузенов по имени Энтони, Беатрис, Кристофер, Даниэль и Элизабет. Как кузены, все они связаны друг с другом.

1) Давайте поместим Энтони в Коллекцию №1. 2) Давайте поместим Беатрис в Коллекцию №1. 3) Кристофер пройдет через наш алгоритм ... мы не можем поместить его в коллекции №1, так как это будет треугольник. Мы помещаем его в Сборник №2. 4) Идет Даниэль. Мы не можем поместить его в коллекцию №1, потому что это сформировало бы треугольник, поэтому мы поместили его в Коллекцию №2. 5) А вот и Элизабет. Мы не можем поместить ее в Коллекцию №1, потому что это образовало бы треугольник с Энтони и Беатрис. Мы не можем поместить ее в Сборник № 2, потому что это будет треугольник с Кристофером и Дэниелом.

Даже если мы изменим алгоритм, чтобы поместить Битрюса в Сборник №2, мысленный эксперимент завершится аналогичной проблемой. Переупорядочивание людей вызывает ту же проблему. Как бы вы их ни шагали, пятый человек никуда не может пойти - это разновидность «принципа пидгенхола».

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

Вот идея, которая может сработать. Я сомневаюсь, что это идеальный алгоритм, поэтому другие люди, пожалуйста, опирайтесь на него.

Просмотрите свой график и сначала найдите все треугольники. Я знаю, что это кажется смешным, но я думаю, что это было бы неплохо с точки зрения класса сложности. Вы можете найти любые треугольники, частью которых является данный узел, просто пройдя по всем его краям три шага и посмотрев, дойдете ли вы до того места, где начали. (Я подозреваю, что есть способ получить все треугольники в графе, который быстрее, чем просто найти треугольники для каждого узла.)

Когда у вас есть треугольники, вы сможете разделить их любым удобным для вас способом. По определению, как только вы их разделите, треугольников больше не останется, поэтому я не думаю, что вам нужно беспокоиться о связях между треугольниками или смежными треугольниками или о чем-то подобном.

Думаю, в этой задаче используется алгоритм O (n ^ 5), где n - количество вершин.