Задача про клікове покриття

обчислювальна задача в теорії графів

Задача про клікове покриття — обчислювальна задача, яка полягає у визначенні можливості розбити вершини графу на клік. Є NP-повною; входить до числа 21 NP-повних задач Карпа[1].

Якщо дано розбиття вершин на множин, то можна за поліноміальний час визначити, що кожна множина утворює кліку так, що задача належить до класу NP. NP-повнота задачі про клікове покриття випливає зі зведення її до задачі розфарбовування графу: розкладання графу на клік відповідає знаходженню розкладу вершин доповнення на незалежних множин (кожній із цих множин можна призначити один колір, що дасть -розфарбування).

Найменший розмір клікового покриття графу — найменше число , для якого клікове покриття існує.

Пов'язана задача знаходження числа перетинів розглядає множини клік, що включають усі ребра даного графу; ця задача також NP-повна.

Примітки ред.

  1. Карп, 1975, с. 16—38.

Література ред.

  • Richard Karp. [1] / R. E. Miller, J. W. Thatcher. — Plenum Press, 1972. — С. 85—103. Архівовано з джерела 29 червня 2011
    • P. M. Карп. Кибернетический сборник (новая серия) / О. Б. Лупанов. — М. : «Мир», 1975. — С. 16—38.
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5. A1.2: GT19, стр. 194.
    • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М. : «Мир», 1982.