Установить задачу разделения
 | Эта статья может быть слишком технической для понимания большинства читателей . ( Май 2017 г. ) |
В теории сложности вычислений проблема разделения множества представляет собой следующую проблему решения : для данного семейства F подмножеств конечного множества S решить, существует ли разбиение S на два подмножества S 1 , S 2 такое, что все элементы F являются разделен этим разбиением, т. е. ни один из элементов F не находится полностью в S 1 или S 2 . Расщепление множеств — одна из задач Гэри и Джонсона классических NP-полных . [ 1 ] Эту проблему иногда называют 2-раскрашиваемостью гиперграфа .
Варианты
[ редактировать ]Оптимизационная версия этой проблемы называется разделением максимального множества и требует нахождения раздела, который максимизирует количество разделенных элементов F . Это APX-полный [ 2 ] проблема и следовательно в НКО .
Проблема множества k разделения формулируется следующим образом: учитывая S , F и целое число k , существует ли раздел S , который разбивает по крайней мере k подмножеств F ? Исходная формулировка представляет собой ограниченный случай, когда k равно мощности F . Set k -Splitting является управляемым с фиксированными параметрами , т. е. если k считается фиксированным параметром, а не частью входных данных, то полиномиальный алгоритм существует для любого фиксированного k . Дене, Феллоуз и Розамонд представили алгоритм, который решает ее вовремя. для некоторой функции f и константы c . [ 3 ]
Когда каждый элемент F ограничен до мощности ровно k , вариант решения называется разделением E k -множества , а версия оптимизации max - расщеплением E k -множества . При k > 2 первый остается NP-полным, а при k ≥ 2 второй остается APX-полным. [ 4 ] Для k ≥ 4 разделение E k -Set устойчиво к аппроксимации. То есть, если P = NP, не существует алгоритма аппроксимации с полиномиальным временем (фактором) , который работал бы существенно лучше, чем случайное разбиение. [ 5 ] [ 6 ]
— Разделение взвешенного набора это вариант, в котором подмножества в F имеют веса, и цель состоит в том, чтобы максимизировать общий вес разделенных подмножеств.
Связь с другими проблемами
[ редактировать ]Расщепление множеств является частным случаем проблемы не все равной выполнимости без отрицательных переменных. Кроме того, расщепление E k -множества равно немонохроматической графа гиперграфов k -однородных раскраске . При k =2 вариант оптимизации сводится к известному максимальному разрезу . [ 6 ]
Ссылки
[ редактировать ]- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5 .
- ^ Петранк, Эрез (1994). «Трудность аппроксимации: расположение пробела». Вычислительная сложность . 4 (2). Спрингер : 133–157. дои : 10.1007/BF01202286 . S2CID 16433553 .
- ^ Дене, Франк; Ребята, Майкл; Розамонд, Фрэнсис (2003). Алгоритм FPT для разделения множеств (PDF) . Концепции теории графов в информатике (WG2003), Конспекты лекций по информатике . Том. 2880. Спрингер . стр. 180–191.
- ^ Ловас, Ласло (1973). Покрытия и раскраски гиперграфов . 4-я Юго-Восточная конференция по комбинаторике, теории графов и информатике.
- ^ Хостад, Йохан (2001). «Некоторые оптимальные результаты неаппроксимируемости». Журнал АКМ . 48 (4). Ассоциация вычислительной техники : 798–859. дои : 10.1145/502090.502098 . S2CID 5120748 .
- ^ Jump up to: а б Гурусвами, Венкатесан (2003). «Результаты неаппроксимируемости для задач разделения множеств и выполнимости без смешанных предложений». Алгоритмика . 38 (3). Спрингер : 451–469. дои : 10.1007/s00453-003-1072-z . S2CID 15541433 .