В теории графов покрытие кликами или разбиение на клики заданного неориентированного графа — это набор клик , которые покрывают весь граф. Минимальное покрытие кликами — это покрытие кликами, которое использует как можно меньше клик. Минимальное k , для которого существует покрытие кликами, называется числом покрытия кликами заданного графа.
Покрытие кликами графа G можно рассматривать как раскраску графа дополнения графа G , графа на том же множестве вершин, который имеет ребра между несмежными вершинами G . Подобно покрытиям кликами, раскраски графов являются разбиениями множества вершин, но на подмножества без смежностей ( независимые множества ), а не на клики. Подмножество вершин является кликой в G тогда и только тогда, когда оно является независимым множеством в дополнении к G , поэтому разбиение вершин G является покрытием кликами G тогда и только тогда, когда оно является раскраской дополнения к G .
Задача покрытия клик в теории вычислительной сложности — это алгоритмическая задача нахождения минимального покрытия клик или (перефразируя как задача принятия решения ) нахождения покрытия клик, число клик в котором меньше заданного порога. Нахождение минимального покрытия клик является NP-трудной задачей , а ее версия решения является NP-полной задачей . Это была одна из 21 оригинальной задачи Ричарда Карпа, которая была показана как NP-полная в его статье 1972 года «Сводимость среди комбинаторных задач». [1]
Эквивалентность между покрытиями кликами и раскраской является сведением , которое можно использовать для доказательства NP-полноты задачи покрытия кликами из известной NP-полноты раскраски графа. [2]
Совершенные графы определяются как графы, в которых для каждого индуцированного подграфа хроматическое число (минимальное число цветов в раскраске) равно размеру максимальной клики . Согласно теореме о слабом совершенном графе , дополнение совершенного графа также является совершенным. Следовательно, совершенные графы также являются графами, в которых для каждого индуцированного подграфа число покрытия кликой равно размеру максимального независимого множества . В совершенных графах можно вычислить число покрытия кликой за полиномиальное время .
Другим классом графов, в которых минимальное покрытие кликой может быть найдено за полиномиальное время, являются графы без треугольников . В этих графах каждое покрытие кликой состоит из сопоставления (множества непересекающихся пар смежных вершин) вместе с синглтонными множествами для оставшихся несопоставленных вершин. Количество клик равно количеству вершин за вычетом количества сопоставленных пар. Поэтому в графах без треугольников минимальное покрытие кликой может быть найдено с помощью алгоритма для максимального сопоставления .
Оптимальное разбиение на клики также может быть найдено за полиномиальное время для графов с ограниченной кликовой шириной . [3] К ним относятся, среди прочих графов, кографы и дистанционно-наследуемые графы , которые также являются классами совершенных графов.
Задача покрытия кликой остаётся NP-полной на некоторых других специальных классах графов, включая кубические планарные графы [4] и графы единичных дисков . [5]
Та же самая твердость результатов аппроксимации, которая известна для раскраски графов, применима и к покрытию клик. Поэтому, если только P = NP , не может быть полиномиального алгоритма аппроксимации для любого ε > 0 , который на графах с n вершинами достигает коэффициента аппроксимации лучше, чем n 1 − ε . [6]
В графах, где каждая вершина имеет не более трех соседей , покрытие кликой остается NP-трудным, и существует константа ρ > 1, такая, что его NP-трудно аппроксимировать с коэффициентом аппроксимации ρ или лучше. Тем не менее, за полиномиальное время можно найти аппроксимацию с коэффициентом 5/4. То есть, этот алгоритм аппроксимации находит покрытие кликой, количество клик в котором не более чем в 5/4 раз больше оптимального. [4]
Метод Бейкера может быть использован для предоставления полиномиальной по времени аппроксимационной схемы для задачи на планарных графах. [7]
Связанная с этим задача покрытия ребер кликами касается разбиения ребер графа, а не вершин, на подграфы, индуцированные кликами. Она также является NP-полной. [8]