Нажмите на обложку
В теории графов кликовое покрытие или разбиение на клики данного неориентированного графа — это совокупность клик, покрывающих весь граф. Минимальное покрытие клик — это покрытие клик, которое использует как можно меньше клик. Минимальное значение 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]
Ссылки
[ редактировать ]- ^ Карп, Ричард (1972), «Сводимость среди комбинаторных задач» (PDF) , в Miller, RE; Тэтчер, Дж. У. (ред.), Труды симпозиума по сложности компьютерных вычислений , Plenum Press, стр. 85–103, заархивировано из оригинала (PDF) 29 июня 2011 г. , получено 29 августа 2008 г.
- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 A1.2: GT19, стр. 194.
- ^ Эспелаж, Вольфганг; Гурски, Фрэнк; Ванке, Эгон (2001), «Как решить NP-трудные задачи с графами на графах с ограниченной шириной клика за полиномиальное время», Международный семинар по теоретико-графовым концепциям в информатике (WG 2001) , Конспекты лекций по информатике, том. 2204, Springer, стр. 117–128, doi : 10.1007/3-540-45477-2_12 .
- ^ Jump up to: Перейти обратно: а б Чериоли, MR; Фариа, Л.; Феррейра, ТО; Мартинхон, CAJ; Протти, Ф.; Рид, Б. (июнь 2008 г.), «Разбиение на клики кубических графов: плоский случай, сложность и аппроксимация», Discrete Applied Mathematics , 156 (12): 2270–2278, doi : 10.1016/j.dam.2007.10.015 .
- ^ Думитреску, Адриан; Пах, Янош (2009), «Минимальное разбиение клики в графах единичных дисков», arXiv : 0909.1552 [ cs.CG ] .
- ^ Цукерман, Д. (2007), «Экстракторы линейных степеней и неаппроксимируемость максимальной клики и хроматического числа» (PDF) , Теория вычислений , 3 : 103–128, doi : 10.4086/toc.2007.v003a006 .
- ^ Бланшетт, Матье; Ким, Итан; Ветта, Адриан (январь 2012 г.), «Кликовое покрытие на разреженных сетях», 2012 г., Материалы четырнадцатого семинара по разработке алгоритмов и экспериментам (ALENEX) , Общество промышленной и прикладной математики, стр. 93–102, doi : 10.1137/1.9781611972924. 10
- ^ Гари и Джонсон (1979) , Задача GT59.