Quelle est la complexité de ce problème de couverture?

Edit: j'ai d'abord mal formulé ma contrainte (2), elle est maintenant corrigée. J'ai également ajouté plus d'informations et d'exemples.

Avec certains collègues, étudiant une autre question algorithmique, nous avons pu réduire notre problème au problème intéressant suivant, mais nous n'avons pas pu résoudre la question de sa complexité. Le problème est le suivant.

Instance: un entier , un entier et un ensemble de paires de l'ensemble .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\}$

Question: Existe - t-il un ensemble de taille tel que pour chaque élément de : (1) si , l'intervalle est inclus dans un intervalle défini par une paire dans , et (2) au moins l'un de , appartient à une paire de ? (2) appartient à une paire de .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'$

Exemple
L'ensemble est une solution réalisable (en supposant que est pair): la paire assure la condition (1), tandis que toutes les autres paires assurent la condition (2).n { 1 , n $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$$n$$\{1,n\}$

Remarques
(I) Puisque chaque paire contient exactement deux éléments, pour remplir la condition (2), nous avons besoin d'au moins paires. BTW cela implique une approximation 2 triviale en renvoyant le entier , puisque nous supposons . S| S| ≤$\frac{n}{2}$$S$$|S|\leq n$

(II) Une autre façon de voir le problème est de considérer une échelle à $n$ étapes (comme celle ci-dessous ), avec un ensemble $S$ de $n$ cycles de l'échelle. Chaque pas de l'échelle correspond à un élément et chaque bord latéral est un intervalle $[i,i+1]$ . Un cycle comprenant les étapes $s,t$ correspond exactement à une paire $\{s,t\}$ : il couvre tous les intervalles consécutifs entre $s$ et $t$ , et il s'arrête à la fois $s$ et $t$ .
La question est alors de savoir s'il existe un ensemble $S'\subseteq S$ de $k$cycles dont l'union couvre tous les bords de l'échelle (y compris les bords de marche et les bords latéraux).

(III) Si l'on ne demandait que la condition (1), le problème correspondrait au problème d'ensemble dominant dans un graphe d'intervalles défini à partir des intervalles donnés par les paires de avec de petits intervalles supplémentaires pour chaque dans . Ce problème est classiquement résoluble en temps linéaire (voir par exemple ici ). De même, si l'on demandait simplement la condition (2), cela pourrait être réduit au problème de couverture de bord (les sommets sont les éléments, les bords sont les paires), qui est également résolu en temps polynomial par une approche de correspondance maximale.S [ i + ϵ , i + 1 - ϵ ] i { 1 , … , n - 1 $[s_i,t_i]$$S$$[i+\epsilon,i+1-\epsilon]$$i$$\{1,\ldots, n-1\}$

Donc ma question est dans le titre:

Ce problème est-il en P? Est-il NP-complet?

Toute référence à un problème similaire est la bienvenue.

Bien que cela ne résout pas la question que vous posez, certains des commentaires précédents considèrent les algorithmes d'approximation. FWIW, je pense qu'un PTAS (schéma d'approximation poly-temps) est possible en utilisant la programmation dynamique. Voici l'idée.

Étant donné n'importe quelle instance et , créez une solution comme suit. Marquez chaque ( 1 / ϵ ) ième sommet. Pour chaque sommet i marqué , parmi toutes les arêtes ( j , k ) qui "s'étendent" i (c'est-à-dire qui satisfont à la contrainte (1) pour i ), choisissez une arête qui minimise j et une qui minimise maximise k . Ajoutez ces 2 ϵ n bords à la solution.$\epsilon > 0$$(1/\epsilon)$$i$$(j,k)$$i$$i$$j$$k$$2 \epsilon n$

$2n\epsilon$$O(\epsilon \mbox{OPT})$

$1/\epsilon$

$1/\epsilon$$1/\epsilon$$1/\epsilon$$1/\epsilon^2$

$i$$(C_i, C_{i+1})$$F_i(C_i,C_{i+1})$$S$$C_i\cup S \cup C_{i+1}$$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$