Меня интересует параметризованная сложность того, что я буду называть проблемой d-мерного ударного множества: с учетом пространства диапазона (т. Е. Системы множеств / гиперграфа) S = (X, R) с VC-размерностью не более d и натуральное число k, содержит ли X подмножество размера k, которое попадает в каждый диапазон в R? Параметризованная версия задачи параметризована как k.
Для каких значений d это задача d-мерного набора ударов
- в FPT?
- в W [1]?
- W [1] -Жесткий?
- W [2] -Жесткий?
То, что я знаю, можно резюмировать следующим образом:
1-мерный ударный набор находится в P и, следовательно, в FPT. Если S имеет размерность 1, то нетрудно показать, что либо существует ударный набор размера 2, либо матрица инцидентности S полностью сбалансирована. В любом случае мы можем найти минимальное множество удара за полиномиальное время.
4-мерный ударный набор - W [1] -твердый. Dom, Fellows и Rosamond [PDF] доказали W [1] -твердость в задаче о нанесении параллельных осям прямоугольников в R ^ 2 осевыми параллельными линиями. Это может быть сформулировано как Ударная совокупность в пространстве диапазона VC-измерения 4.
Если никакое ограничение не наложено на d, то у нас есть стандартная проблема Hitting Set, которая является W [2] -полной и NP-полной.
Лангерман и Морин [citeseer link] дают алгоритмы FPT для Set Cover в ограниченном измерении, хотя их модель ограниченной размерности не совпадает с моделью, определенной ограниченной VC-размерностью. Их модель, по-видимому, не включает, например, проблему попадания в полупространства точками, хотя задача прототипа для их модели эквивалентна попаданию в гиперплоскости с точками.
Ответы:
Я думаю, что эта проблема слишком сложна. Мы не знаем ответа на гораздо более простые проблемы в этой семье. Например, учитывая набор из n точек на плоскости и набор (скажем, n) единичных дисков, решите, имеется ли покрытие точек на k единичных дисков. Для этого существует простой n ^ O (k) алгоритм времени, и я не удивлюсь, если используя известные идеи, можно сделать n ^ O (sqrt {k}) (но даже это не очевидно), но выполнить f ( k) * n ^ {O (1)} открыто, и на самом деле было бы довольно интересно. Аппроксимация (1 + eps) следует из работы Мустафы и Рэя http://portal.acm.org/citation.cfm?id=1542362.1542367 .
Кстати, для непрерывной версии, где разрешен любой диск, можно решить проблему за n ^ {O (k)} время. PTAS в этом случае также довольно прост с использованием сдвинутых сеток.
источник
Мы решаем этот вопрос в новом препринте: http://arxiv.org/abs/1512.00481
Ударная совокупность в гиперграфах низкой VC-размерности (Карл Брингман, Ласло Козма, Шай Моран, Н.С. Нараянасвами).
Оказывается, что Ударная совокупность является W [1] -твердой уже, когда VC-размерность равна 2.
источник
Даниэль Маркс: Эффективные схемы аппроксимации для геометрических задач . ESA 2005: 448-459 довольно актуально.
источник