Jaka jest złożoność tego problemu obejmującego?

Edycja: Najpierw źle sformułowałem moje ograniczenie (2), teraz jest poprawione. Dodałem także więcej informacji i przykładów.

Z niektórymi kolegami, badającymi inne pytania algorytmiczne, byliśmy w stanie zredukować nasz problem do następującego interesującego problemu, ale nie byliśmy w stanie rozwiązać problemu jego złożoności. Problem jest następujący.

Przykład: całkowita oznacza liczbę całkowitą , a zestaw o par z zestawu .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\}$

Pytanie: Czy istnieje zestaw o rozmiarze taki, że dla każdego elementu z : (1) jeśli , przedział wynosi zawarty w pewnym przedziale zdefiniowanym przez parę w , i (2) co najmniej jeden z , należy do jakiejś pary ? (2) należy do jakiejś pary .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'$

Przykład
Zestaw jest wykonalnym rozwiązaniem (zakładając, że jest parzyste): para zapewnia warunek (1), podczas gdy wszystkie inne pary zapewniają warunek (2).n { 1 , n $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$$n$$\{1,n\}$

Uwagi
(I) Ponieważ każda para zawiera dokładnie dwa elementy, aby spełnić warunek (2), potrzebujemy co najmniej par. BTW oznacza to trywialne przybliżenie 2 przez zwrócenie całego , ponieważ zakładamy, że . S| S| ≤$\frac{n}{2}$$S$$|S|\leq n$

(II) Innym sposobem patrzenia na problem jest rozważenie drabiny z kroków (takie jak te, poniżej ), wraz z zestawem z cykli drabiny. Każdy stopień drabiny odpowiada elementowi, a każda krawędź boczna to przedział . Cykl tym etapy odpowiada dokładnie pary : obejmuje wszystkie kolejne odstępy między i , i zatrzymuje się na obu i . Pytanie brzmi zatem, czy istnieje zbiór z$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$cykle, których łączenie obejmuje wszystkie krawędzie drabiny (w tym krawędzie stopni i krawędzie boczne).

(III) Gdyby ktoś prosił tylko o warunek (1), problem odpowiadałby dominującemu problemowi zadanemu na pewnym wykresie interwałowym określonym na podstawie przedziałów podanych przez pary wraz z dodatkowymi małymi przedziałami dla każdego w . Ten problem można klasycznie rozwiązać w czasie liniowym (patrz np. Tutaj ). Podobnie, jeśli ktoś pyta tylko o warunek (2), można to sprowadzić do problemu pokrycia krawędzi (wierzchołki są elementami, krawędzie są parami), który jest również rozwiązany w czasie wielomianowym przez podejście maksymalnego dopasowania.S [ i + ϵ , i + 1 - ϵ ] i { 1 , … , n - 1 $[s_i,t_i]$$S$$[i+\epsilon,i+1-\epsilon]$$i$$\{1,\ldots, n-1\}$

Więc moje pytanie jest w tytule:

Czy to problem w P? Czy jest kompletny NP?

Wszelkie odniesienia do podobnego problemu są mile widziane.

Chociaż to nie rozwiązuje postawionego pytania, niektóre z poprzednich komentarzy rozważają algorytmy aproksymacyjne. FWIW, myślę, że PTAS (schemat aproksymacji czasu) jest możliwy przy użyciu programowania dynamicznego. Oto pomysł.

Biorąc pod uwagę dowolną instancję i , zbuduj rozwiązanie w następujący sposób. Zaznacz każdy ( 1 / ϵ ) 'wierzchołek. Dla każdego zaznaczonego wierzchołka i spośród wszystkich krawędzi ( j , k ), które „rozpinają” i (tj. Które spełniają ograniczenie (1) dla i ), wybierz jedną krawędź, która minimalizuje j, i jedną, która minimalizuje maksymalizację k . Dodanie tych 2 ε n krawędzie roztworu.$\epsilon > 0$$(1/\epsilon)$$i$$(j,k)$$i$$i$$j$$k$$2 \epsilon n$

Krawędzie te spełniają ograniczenia typu (1) dla wielu wierzchołków. Tymczasem wnoszą do rozwiązania krawędzi, czyli tylko O ( ϵ OPT ) . Na zakończenie znajdziemy optymalne rozwiązanie pozostałego problemu znalezienia zestawu krawędzi, który spełnia wszystkie pozostałe ograniczenia typu (1) i typu (2).$2n\epsilon$$O(\epsilon \mbox{OPT})$

Zdefiniuj „blok” wierzchołków, który będzie zbiorem kolejnych wierzchołków, których ograniczenia typu (1) są spełnione przez dodane do tej pory krawędzie. Między dowolnymi dwoma kolejnymi blokami znajduje się sekwencja wierzchołków, których ograniczenia typu (1) nie są spełnione. (Każda taka sekwencja ma długość co najwyżej , ponieważ zaznaczone wierzchołki mają ograniczenia typu (1) spełnione przez już dodane krawędzie.) Nazwij każdą taką sekwencję „sąsiedztwem” dwóch sąsiednich bloków (więc każdy blok ma sąsiedztwo po lewej i sąsiedztwo po prawej).$1/\epsilon$

W obrębie każdego sąsiedztwa, dla każdego wierzchołka w sąsiedztwie, każda krawędź opuszczająca wierzchołek rozciąga się na odległość co najwyżej (ponieważ krawędź nie obejmuje żadnego zaznaczonego wierzchołka). Zatem wierzchołek ma stopień co najwyżej 1 / ϵ . Zatem każde sąsiedztwo ma maksymalnie 1 / ϵ wierzchołków i dotyka co najwyżej 1 / ϵ 2 krawędzi. Nazwij dowolny podzbiór tych krawędzi „konfiguracją” otoczenia. Jeśli konfiguracja spełnia wszystkie ograniczenia typu (1) i typu (2) dla wierzchołków w sąsiedztwie, nazwij konfigurację „prawidłową”.$1/\epsilon$$1/\epsilon$$1/\epsilon$$1/\epsilon^2$

Dla każdego bloku , dla każdej pary ( C i , C i + 1 ) prawidłowych konfiguracji dwóch sąsiedztw bloku, oblicz (w czasie wielomianowym, używając maksymalnego dopasowania itp.) Minimalną wielkość F i ( C i , C i +) 1 ) z każdego zestawu S krawędzi (jeśli istnieją), tak, że krawędzie w C ı ∪ S ∪ C ı + 1 spotykają typu (2) ograniczenia dla wierzchołków w bloku. Ponieważ jest ich najwyżej 2 $i$$(C_i, C_{i+1})$$F_i(C_i,C_{i+1})$$S$$C_i\cup S \cup C_{i+1}$konfiguracjeO(1), można to zrobić w czasie wielomianowym (dla ustalonego eps). $2^{1/\epsilon^2} = O(1)$

Teraz można rozwiązać oryginalnej instancji stwierdzając sekwencję ważnych konfiguracjach, po jednym dla każdej dzielnicy, który minimalizuje Ď I | D i | + F i ( D i , D i + 1 ) , gdzie F i ma znaczenie określone w poprzednim akapicie. Można tego dokonać, znajdując najkrótszą ścieżkę na wykresie utworzoną przez wszystkie prawidłowe konfiguracje, z przewagą kosztów | D i | $D_1, D_2, .., D_k$$\sum_i |D_i| + F_i(D_i, D_{i+1})$$F_i$ z każdej konfiguracji D i dla sąsiedztwa i do każdej konfiguracji D i + 1 dla sąsiedztwa i + 1 . (Ten wykres ma rozmiar O ( 2 1 / ϵ 2 n ) , czyli O ( n ) dla ustalonego ϵ .)$|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$