В теории графов , A клика крышка или разбиение на клики данного неориентированного графа является разбиением из вершин графа в клики , подмножество вершин , внутри которой каждые две вершин смежны. Минимальная клика крышка является кликой крышки , которая использует в качестве несколько кликов , как это возможно. Минимальное k, для которого существует кликовое покрытие, называется числом кликового покрытия данного графа.
Отношение к раскраске [ править ]
Клика крышку графы G можно рассматривать как раскраски графа в дополнении графа из G , граф на то же множество вершин , который имеет ребро между несмежными вершинами G . Как и покрытия клик, раскраски графов - это разбиения множества вершин, но на подмножества без примыканий ( независимые множества ), а не на клики. Подмножество вершин является кликой в G тогда и только тогда, когда оно является независимым множеством в дополнении к G , поэтому разбиение вершин G является кликовым покрытием G тогда и только тогда, когда оно является раскраской дополнения к G. G .
Вычислительная сложность [ править ]
Проблема покрытия клики в теории сложности вычислений - это алгоритмическая проблема поиска минимального покрытия клики или (перефразируемая как проблема решения ) нахождения покрытия клики, количество клик которого меньше заданного порога. Найти минимальное покрытие клики NP-сложно , а его вариант решения является NP-полным . Это была одна из оригинальных 21 проблем Ричарда Карпа, показанных NP-полной в его статье 1972 года «Сводимость среди комбинаторных проблем». [1]
Эквивалентность кликовых покрытий и раскраски - это редукция, которую можно использовать для доказательства NP-полноты проблемы клик-покрытий на основе известной NP-полноты раскраски графов. [2]
В специальных классах графиков [ править ]
Совершенные графы определяются как графы, в которых для каждого индуцированного подграфа хроматическое число (минимальное количество цветов в раскраске) равно размеру максимальной клики . Согласно теореме о слабом совершенном графе , дополнение к совершенному графу также совершенно. Следовательно, идеальные графы - это также графы, в которых для каждого индуцированного подграфа число кликового покрытия равно размеру максимального независимого множества . Число кликовых покрытий в совершенных графах можно вычислить за полиномиальное время .
Другой класс графов, в которых минимальное кликовое покрытие может быть найдено за полиномиальное время, - это графы без треугольников . В этих графах каждое покрытие клики состоит из паросочетания (набора непересекающихся пар смежных вершин) вместе с одноэлементными множествами для оставшихся несовпадающих вершин. Количество клик равно количеству вершин за вычетом количества совпавших пар. Следовательно, в графах без треугольников минимальное покрытие клики может быть найдено с помощью алгоритма максимального соответствия .
Оптимальное разбиение на клики также может быть найдено за полиномиальное время для графов ограниченной ширины клики . [3] К ним относятся, среди прочих графов, кографы и графы с дистанционной наследственностью , которые также являются классами совершенных графов.
Приближение [ править ]
Та же жесткость результатов аппроксимации, которая известна раскраской графа, применима и к покрытию клик. Следовательно, если P = NP , не может быть никакого алгоритма аппроксимации с полиномиальным временем для любого ε > 0, который на n- вершинных графах достигает коэффициента аппроксимации лучше, чем n 1 - ε . [4]
В графах, где каждая вершина имеет не более трех соседей , покрытие клики остается NP-трудным, и существует константа ρ > 1 такая, что ее NP-трудно аппроксимировать с коэффициентом аппроксимации ρ или лучше. Тем не менее, за полиномиальное время можно найти приближение с соотношением 5/4. То есть этот алгоритм аппроксимации находит покрытие клики, количество клик которого не более чем в 5/4 раз превышает оптимальное. [5]
Связанные проблемы [ править ]
Связанная с этим проблема покрытия ребер клики касается разбиения ребер графа, а не вершин, на подграфы, индуцированные кликами. Он также является NP-полным. [6]
Ссылки [ править ]
- ^ Карп, Ричард (1972), «Сводимость среди комбинаторных проблем» (PDF) , Миллер, RE; Тэтчер, JW (ред.), Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press, стр. 85–103 , получено 29 августа 2008 г.
- ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 A1.2: GT19, стр.194.
- ^ Эспелаж, Вольфганг; Гурски, Франк; Ванке, Эгон (2001), «Как решить NP-сложные графовые задачи на графах с ограниченной шириной клики за полиномиальное время», Международный семинар по теоретико-графическим концепциям в компьютерных науках (WG 2001) , Lecture Notes in Computer Science, 2204 , Springer, стр. 117–128, DOI : 10.1007 / 3-540-45477-2_12.
- ^ Цукерман, D. (2007), "степень экстракторы Линейных и inapproximability Макса клики и хроматическое число" (PDF) , теории вычислений , 3 : 103-128, DOI : 10.4086 / toc.2007.v003a006 .
- ^ Cerioli, MR; Faria, L .; Феррейра, штат Коннектикут; Мартинхон, CAJ; Protti, F .; Рид, B. (июнь 2008), "Partition в клики для кубических графов: Planar случая, сложность и аппроксимацию", дискретная Прикладная математика , 156 (12): 2270-2278, DOI : 10.1016 / j.dam.2007.10.015.
- ^ Garey & Johnson (1979) , проблема GT59.
