Wie komplex ist dieses Abdeckungsproblem?

Bearbeiten: Ich habe meine Einschränkung (2) zuerst falsch formuliert, sie ist jetzt korrigiert. Ich habe auch weitere Informationen und Beispiele hinzugefügt.

Mit einigen Kollegen, die sich mit einer anderen algorithmischen Frage befassten, konnten wir unser Problem auf das folgende interessante Problem reduzieren, die Frage nach der Komplexität konnten wir jedoch nicht lösen. Das Problem ist wie folgt.

Instanz: Eine ganze Zahl , eine ganze Zahl und eine Menge von Paaren aus der Menge .$n$$k<n$$S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$$n$$\{1,\ldots,n\}$

Frage: Gibt es einen Satz der Größe , so dass für jedes Element von : (1) wenn , das Intervall ist , in einem Intervall das durch ein Paar in , und (2) mindestens eines von , zu einem Paar von ? (2) gehöre zu einem Paar von .$S'\subseteq S$$k$$i$$\{1,\ldots,n\}$
$i<n$$[i,i+1]$$[s_i,t_i]$$S'$
$i$$i+1$$S'$
$i$$S'$

Beispiel
Die Menge ist eine praktikable Lösung (vorausgesetzt, ist gerade): das Paar stellt die Bedingung (1) sicher, während alle anderen Paare die Bedingung (2) sicherstellen.$\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$$n$$\{1,n\}$

Anmerkungen
(I) Da jedes Paar genau zwei Elemente enthält, benötigen wir mindestens Paare , um die Bedingung (2) zu erfüllen . Übrigens impliziert dies eine triviale 2-Approximation durch Rückgabe des gesamten , da wir annehmen .$\frac{n}{2}$$S$$|S|\leq n$

(II) Eine andere Art, das Problem zu betrachten, besteht darin, eine Leiter mit Stufen (wie die folgende ) zusammen mit einer Menge von Zyklen der Leiter zu betrachten. Jede Stufe der Leiter entspricht einem Element, und jede Seitenkante ist ein Intervall . Ein Zyklus mit den Schritten entspricht genau einem Paar : Er deckt alle aufeinander folgenden Intervalle zwischen und und stoppt sowohl bei als auch bei . Die Frage ist dann, ob es eine Menge von$n$$S$$n$$[i,i+1]$$s,t$$\{s,t\}$$s$$t$$s$$t$
$S'\subseteq S$$k$Zyklen, deren Vereinigung alle Kanten der Leiter abdeckt (einschließlich Stufenkanten und Seitenkanten).

(III) Wenn man nur nach Bedingung (1) fragen würde, würde das Problem dem dominierenden Mengenproblem in einem Intervallgraphen entsprechen, der aus den Intervallen die durch die Paare von zusammen mit zusätzlichen winzigen Intervallen für jedes in . Dieses Problem ist klassisch in linearer Zeit lösbar (siehe zB hier ). In ähnlicher Weise könnte man, wenn man nur nach Bedingung (2) fragt, dieses Problem auf das Randbedeckungsproblem reduzieren (Eckpunkte sind die Elemente, Kanten sind die Paare), das auch durch einen Maximum-Matching-Ansatz polynomial-zeitlich lösbar ist.$[s_i,t_i]$$S$$[i+\epsilon,i+1-\epsilon]$$i$$\{1,\ldots, n-1\}$

Meine Frage steht also im Titel:

Ist das Problem in P? Ist es NP-vollständig?

Jeder Hinweis auf ein ähnliches Problem ist willkommen.

Obwohl dies die von Ihnen aufgeworfene Frage nicht löst, berücksichtigen einige der vorherigen Kommentare Approximationsalgorithmen. FWIW denke ich, dass ein PTAS (Poly-Time Approximation Schema) mit dynamischer Programmierung möglich ist. Hier ist die Idee.

Erstellen Sie bei einer gegebenen Instanz und eine Lösung wie folgt. Markiere jeden -ten Eckpunkt. Wählen Sie für jeden markierten Scheitelpunkt aus allen Kanten , die "überspannen" (dh die die Bedingung (1) für erfüllen ), eine Kante, die minimiert, und eine, die maximiert . Fügen Sie diese Kanten zur Lösung hinzu.$\epsilon > 0$$(1/\epsilon)$$i$$(j,k)$$i$$i$$j$$k$$2 \epsilon n$

Diese Kanten erfüllen die Bedingungen von Typ (1) für viele Scheitelpunkte. In der Zwischenzeit tragen sie Kanten zur Lösung bei, die nur . Abschließend finden wir eine optimale Lösung für das verbleibende Problem, eine Reihe von Kanten zu finden, die alle verbleibenden Einschränkungen von Typ (1) und Typ (2) erfüllen.$2n\epsilon$$O(\epsilon \mbox{OPT})$

Definieren Sie einen "Block" von Scheitelpunkten als eine Menge aufeinanderfolgender Scheitelpunkte, deren Typ (1) -Einschränkungen von den bisher hinzugefügten Kanten erfüllt werden. Zwischen zwei aufeinanderfolgenden Blöcken befindet sich eine Folge von Scheitelpunkten, deren Typ (1) -Einschränkungen nicht erfüllt sind. (Jede solche Sequenz hat eine Länge von höchstens , da die Typ (1) -Beschränkungen der markierten Scheitelpunkte durch die bereits hinzugefügten Kanten erfüllt werden.) Nennen Sie jede solche Sequenz eine "Nachbarschaft" der beiden benachbarten Blöcke (also hat jeder Block eine eine Nachbarschaft zu seiner Linken und eine Nachbarschaft zu seiner Rechten).$1/\epsilon$

Innerhalb jeder Nachbarschaft überspannt jede Kante, die den Scheitelpunkt verlässt, für jeden Scheitelpunkt in der Nachbarschaft einen Abstand von höchstens (da die Kante keinen markierten Scheitelpunkt überspannt). Somit hat der Scheitel höchstens einen Grad von . Somit hat jede Nachbarschaft höchstens Eckpunkte und berührt höchstens Kanten. Nennen Sie eine beliebige Teilmenge dieser Kanten eine "Konfiguration" der Nachbarschaft. Wenn eine Konfiguration alle Einschränkungen von Typ (1) und Typ (2) für die Eckpunkte in der Nachbarschaft erfüllt, nennen Sie die Konfiguration "gültig".$1/\epsilon$$1/\epsilon$$1/\epsilon$$1/\epsilon^2$

Berechnen Sie für jeden Block für jedes Paar gültiger Konfigurationen der beiden Nachbarschaften des Blocks (in Polynomzeit, unter Verwendung maximaler Übereinstimmung usw.) die minimale Größe einer beliebigen Menge von Kanten (falls vorhanden), so dass die Kanten in die Typ (2) -Beschränkungen für die Eckpunkte im Block erfüllen. Da es höchstens Konfigurationen gibt, kann dies in Polynomzeit (für festes eps) erfolgen. $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)$

Jetzt können Sie die ursprüngliche Instanz lösen, indem Sie eine Folge gültiger Konfigurationen finden, eine für jede Nachbarschaft, die minimiert , wobei wie im vorherigen Absatz definiert ist. Dies kann durch Auffinden eines kürzesten Pfades in dem von allen gültigen Konfigurationen gebildeten Graphen mit einem Kostenrand von jeder Konfiguration für die Nachbarschaft zu jeder Konfiguration für die Nachbarschaft . (Dieser Graph hat die Größe , was für festes .)$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$