Какова сложность этой проблемы покрытия?

Редактировать: я сначала неправильно сформулировал свое ограничение (2), теперь оно исправлено. Я также добавил больше информации и примеров.

С некоторыми коллегами, изучающими какой-то другой алгоритмический вопрос, мы смогли свести нашу проблему к следующей интересной проблеме, но мы не смогли решить вопрос о ее сложности. Проблема заключается в следующем.

Экземпляр: целое число , целое число и набор из пар из набора .k < n S = { { s 1 , t 1 } , … , { s n , t n } } n { 1 , … , n $n$$k<n$$S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$$n$$\{1,\ldots,n\}$

Вопрос: существует ли набор размера такой, что для каждого элемента из : (1) если , интервал равен входит в некоторый интервал определенный парой в , и (2) хотя бы один из , принадлежит некоторой паре ? (2) принадлежу некоторой паре .k i { 1 , … , n } i < n [ i , i + 1 ] [ s i , t i ] S ′ i i + 1 S ′ i S $S'\subseteq S$$k$$i$$\{1,\ldots,n\}$
$i<n$$[i,i+1]$$[s_i,t_i]$$S'$
$i$$i+1$$S'$
$i$$S'$

Пример
. Множество является возможным решением (при условии, что четно): пара обеспечивает условие (1), тогда как все остальные пары обеспечивают условие (2).n { 1 , n $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$$n$$\{1,n\}$

Замечания
(I) Поскольку каждая пара содержит ровно два элемента, для выполнения условия (2) нам нужно как минимум пар. Кстати, это подразумевает тривиальное 2-приближение, возвращая всю , поскольку мы предполагаем . S| S| ≤$\frac{n}{2}$$S$$|S|\leq n$

(II) Другой способ взглянуть на проблему - рассмотреть лестницу с ступенями (как, например, ниже ), вместе с множеством из циклов лестницы. Каждый шаг лестницы соответствует некоторому элементу, и каждый боковой край является интервалом . Цикл, включающий шаги точно соответствует паре : он охватывает все последовательные интервалы между и и останавливается как на и на . Тогда возникает вопрос, существует ли множество из$n$n [ i , i + 1 ] s , t { s , t } s t s t S ′ ⊆ S $S$$n$$[i,i+1]$$s,t$$\{s,t\}$$s$$t$$s$$t$
$S'\subseteq S$$k$циклы, объединение которых охватывает все ребра лестницы (включая ступеньки и боковые ребра).

(III) Если бы кто-то спрашивал только об условии (1), проблема соответствовала бы задаче о доминирующем множестве в некотором интервальном графе, определенном из интервалов заданных парами вместе с дополнительными крошечными интервалами для каждого в . Эта задача классически разрешима за линейное время (см., Например, здесь ). Точно так же, если бы кто-то просто запрашивал условие (2), это можно было бы свести к проблеме покрытия ребер (вершины - это элементы, ребра - это пары), что также решается за полиномиальное время методом максимального соответствия.S [ i + ϵ , i + 1 - ϵ ] i { 1 , … , n - 1 $[s_i,t_i]$$S$$[i+\epsilon,i+1-\epsilon]$$i$$\{1,\ldots, n-1\}$

Итак, мой вопрос в заголовке:

Эта проблема в P? Это NP-полный?

Любая ссылка на подобную проблему приветствуется.

Хотя это не решает вопрос, который вы поднимаете, в некоторых предыдущих комментариях рассматриваются алгоритмы аппроксимации. FWIW, я думаю, что PTAS (схема аппроксимации по времени) возможна при использовании динамического программирования. Вот идея

Для любого экземпляра и построить решение следующим образом. Отметьте каждую ( 1 / ϵ ) -ю вершину. Для каждой отмеченной вершины i из всех ребер ( j , k ), которые «охватывают» i (т. Е. Которые удовлетворяют ограничению (1) для i ), выберите одно ребро, которое минимизирует j, и то, которое минимизирует, максимизирует k . Добавьте эти 2 е п края к решению.$\epsilon > 0$$(1/\epsilon)$$i$$(j,k)$$i$$i$$j$$k$$2 \epsilon n$

Эти ребра удовлетворяют ограничениям типа (1) для многих вершин. Между тем они вносят ребер в решение, которое составляет только O ( ϵ OPT ) . Чтобы закончить, мы найдем оптимальное решение оставшейся проблемы поиска набора ребер, которое удовлетворяет всем остальным ограничениям типа (1) и типа (2).$2n\epsilon$$O(\epsilon \mbox{OPT})$

Определите «блок» вершин как набор последовательных вершин, ограничения типа (1) которых встречаются с помощью добавленных ребер. Между любыми двумя последовательными блоками существует последовательность вершин, ограничения типа (1) которых не выполняются. (Любая такая последовательность имеет длину не более , потому что отмеченные вершины имеют ограничения типа (1), встречаемые уже добавленными ребрами.) Назовите любую такую ​​последовательность «соседством» двух соседних блоков (поэтому каждый блок имеет соседство слева и соседство справа).$1/\epsilon$

В пределах каждой окрестности, для каждой вершины в окрестности, каждое ребро, выходящее из вершины, охватывает расстояние не более (потому что ребро не охватывает ни одну отмеченную вершину). Таким образом, вершина имеет степень не более 1 / ϵ . Таким образом, каждый район имеет не более 1 / е вершины и штрихи в большинстве 1 / ε 2 ребер. Назовите любое подмножество этих ребер «конфигурацией» окрестности. Если конфигурация удовлетворяет всем ограничениям типа (1) и типа (2) для вершин в окрестности, назовите конфигурацию «действительной».$1/\epsilon$$1/\epsilon$$1/\epsilon$$1/\epsilon^2$

Для каждого блока для каждой пары ( C i , C i + 1 ) действительных конфигураций двух окрестностей блока вычисляют (за полиномиальное время, используя максимальное совпадение и т. Д.) Минимальный размер F i ( C i , C i + 1 ) любого множества S ребер (если оно существует), такого, что ребра в C i ∪ S ∪ C i + 1 удовлетворяют ограничениям типа (2) для вершин в блоке. Так как их максимум 2 $i$$(C_i, C_{i+1})$$F_i(C_i,C_{i+1})$$S$$C_i\cup S \cup C_{i+1}$конфигурации, это можно сделать за полиномиальное время (для фиксированного eps). $2^{1/\epsilon^2} = O(1)$

$D_1, D_2, .., D_k$$\sum_i |D_i| + F_i(D_i, D_{i+1})$$F_i$$|D_i| + F_i(D_i, D_{i+1})$$D_i$$i$$D_{i+1}$$i+1$$O(2^{1/\epsilon^2} n)$$O(n)$$\epsilon$