NP-dureza de una especialización Set Cover

¿El siguiente problema es NP-hard?

Dado un conjunto de números reales (objetivos) x 1 , ... , x N y un "tridente" definido por dos distancias a , b desde el centro del tridente, ¿cuál es el número mínimo K de posiciones p 1 , ... , p K del tridente para cubrir todos los objetivos, es decir, K ⋃ k = 1 { p k - a , p k , p k + b } ⊇ { $N$$x_1,\dotsc,x_N$$a$$b$$K$$p_1,\dotsc,p_K$

Obviamente, este es un caso especial del problema de la cubierta del conjunto : considerando todos los conjuntos , con p k ∈ { x n + t ∣ n ∈ { 1 , … , N } , t ∈ { a , 0 , - b } $\{p_k-a,p_k,p_k+b\}$$p_k\in\{x_n+t\mid n\in\{1,\dotsc,N\}, t\in\{a,0,-b\}\}$representando todas las posiciones potenciales "relevantes", buscamos el número mínimo de conjuntos que cubren el universo . De manera equivalente, podemos representar el problema como un gráfico bipartito de nodos de posición y destino y considerar el problema del conjunto de golpes .$\{x_1,\dotsc,x_N\}$

Tenga en cuenta que el problema no es NP-duro si el tridente pierde una de sus "puntas": entonces cada objetivo puede cubrirse desde 2 posiciones y cada posición cubre como máximo 2 objetivos, por lo que el gráfico bipartito correspondiente de posiciones y objetivos potenciales es un unión de caminos. En cada ruta es fácil determinar un conjunto de golpes mínimos (es decir, los nodos de posición internos).

¿Pero es el caso del tridente NP-duro?

Visión general

$k$$x_i$

Para demostrar que el problema de la cubierta del tridente numérico es NP-hard, presentamos el siguiente problema intermedio, que llamaremos el problema de la cubierta del triángulo de la cuadrícula:

$S \subset \mathbb{Z}^+ \times \mathbb{Z}^+$$k$

$T \subset \mathbb{Z} \times \mathbb{Z}$$|T| \le k$$S \subseteq \bigcup_{(x,y) \in T} \{(x, y), (x, y+1), (x+1, y)\}$

$k$$(1, 1, \sqrt{2})$$(x, y)$$(x, y+1)$$(x+1, y)$

Para mostrar que la cubierta del tridente numérico es NP-hard, proporcionamos dos reducciones: una reducción de Planar 3SAT a la cubierta del triángulo de la cuadrícula y una reducción de la cubierta del triángulo de la cuadrícula a la cubierta del tridente numérico. Juntos, estos se componen en una reducción del problema Planar 3SAT NP-duro al problema de la Cubierta del Tridente Numérico, lo que implica que la Cubierta del Tridente Numérico es NP-duro.

$p + q\sqrt{2}$$p + q\sqrt{2}$$(p, q)$

Reducción 1: de la cubierta del triángulo de la cuadrícula a la cubierta del tridente numérico.

$S \subseteq \mathbb{Z}^+ \times \mathbb{Z}^+$$k$

$x_1, ..., x_N$$a, b$$k'$

$S$$s_1 = (p_1, q_1), s_2 = (p_2, q_2), ..., s_{|S|} = (p_{|S|}, q_{|S|})$$i$$1$$N = |S|$$x_i = -p_i + q_i \sqrt{2}$$a = 1$$b = \sqrt{2}$$k' = k$

Esta reducción es claramente una operación de tiempo polinomial, por lo que lo único que queda por mostrar es que la reducción es preservar la respuesta.

$x_i$$x_i$$x_i + a$$x_i - b$$x_i$$-v_a + v_b \sqrt{2}$$v_a$$v_b$$-v_a + v_b \sqrt{2}$$f$$p + q \sqrt{2}$$f(-v_a + v_b\sqrt{2}) = (v_a, v_b)$$f$$x_i$$s_i$

$-p + q\sqrt{2}$$-(p+1) + q\sqrt{2}$$-p + q\sqrt{2}$$-p + (q+1)\sqrt{2}$$f$$(p,q)$$(p+1, q)$$(p, q+1)$$f$$S$$f^{-1}$$f$

$f$$\{x_1, ..., x_{|S|}\}$$f$$S = \{s_1, ..., s_{|S|}\} = \{f(x_1), ..., f(x_{|S|})\}$$f$$(1,1\sqrt{2})$$x_i$$k$$S$$k$$(1,1\sqrt{2})$

Reducción 2: de 3SAT plano a la cubierta triangular de cuadrícula.

Para esta reducción, se nos da una instancia de 3SAT en forma de un gráfico bipartito plano. Los vértices en una parte corresponden a variables, y los vértices de la otra parte, cada uno de grado 3, corresponden a cláusulas. Cada borde se etiqueta como positivo o negativo, lo que indica de qué manera la variable se incluye en la cláusula (positiva o negativamente).

$(S, k)$$S$$k$

Primero describimos un cable. Un cable consiste en una secuencia de un número impar de puntos (en la red de enteros) donde el primero y el último se llaman terminales, de modo que cada par consecutivo puede estar cubierto por un triángulo sin que el triángulo toque ningún otro punto en el cable. Como ejemplo, considere el siguiente cable:

xoo       x
   o       o
   o ooo   o
   o o  oooo
    oo

$p$$\frac{p+1}{2}$

Aquí mostramos las dos formas de cubrir el ejemplo desde arriba (donde dos puntos están etiquetados con el mismo número si están cubiertos por el mismo triángulo):

x11       9
   2       9
   2 556   8
   3 4  6778
    34

o

112       x
   2       9
   3 566   9
   3 5  7788
    44

Una de las preocupaciones es que podríamos querer conectar dos terminales con un cable, pero no podemos hacerlo porque cualquier "cable" entre esos dos terminales tendría una longitud uniforme. Sin embargo, ese no es el caso: siempre podemos elegir una ruta para que un cable tenga una longitud impar (y, por lo tanto, sea un cable válido). Reemplazar cualquier segmento horizontal de cable de longitud 6 con el siguiente segmento de cable de longitud 7 puede arreglar la paridad de la longitud del cable:

oo  oo
  ooo 

A continuación, presentamos un gadget de cláusula. Una cláusula simplemente conecta uno de los terminales de tres cables de tal manera que si uno de los cables está satisfecho de modo que el terminal compartido esté cubierto, entonces el triángulo que cubre ese terminal compartido no cubre ningún punto de los otros cables:

      o
      o
      o
   ooox
       ooo

Para que el terminal compartido esté cubierto, al menos uno de los tres cables debe estar satisfecho de tal manera que los triángulos que satisfacen el cable no cubran el terminal no compartido de los cables.

Finalmente, presentamos el gadget variable. El gadget variable es un gran bucle similar a un cable (de longitud uniforme) con terminales opcionales que se producen a los lados cada tres filas de la siguiente manera:

oo
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
o o
o ox
o o
 oo

La variable puede crecer verticalmente para acomodar la cantidad necesaria de terminales. Las terminales en filas de paridad par corresponden a ocurrencias positivas de la variable y aquellas en filas de paridad impar corresponden a ocurrencias negativas. Al igual que con el cable, los puntos no terminales del gadget variable pueden satisfacerse utilizando la cantidad mínima de triángulos (la mitad de la cantidad de puntos en el bucle) exactamente de dos maneras. Esos dos ajustes cubren todos los terminales de ocurrencia positiva o todos los terminales de ocurrencia negativa del gadget variable.

Poner todo junto es bastante obvio: construimos el gráfico bipartito usando gadgets variables, gadgets de cláusula (terminales compartidos) y cables que conectan los terminales. El número total de triángulos necesarios para cubrir los puntos no terminales de los cables y las variables es el número objetivo de triángulos.

Claramente, no podemos cubrir toda la cuadrícula con menos triángulos. Además, podemos estar seguros de que los puntos no terminales están cubiertos, ya que las variables y los cables se satisfarán de una de las dos formas descritas. Por lo tanto, la única tarea es satisfacer los terminales.

En cada variable, el dispositivo variable satisfará todos los terminales de ocurrencia positivos o negativos. Los otros terminales en el dispositivo deben ser satisfechos por sus cables conectados. Entonces, los terminales de la cláusula pueden satisfacerse si y solo si cada cláusula está conectada a al menos un cable cuyo otro terminal ya no utilizó el cable (un cable cuyo otro terminal fue satisfecho por su dispositivo variable adjunto). En otras palabras, todos los terminales están satisfechos si y solo si la asignación de variables de acuerdo con la configuración de los gadgets de variables satisface todas las cláusulas.

Como puede ver, la instancia de Grid Triangle Cover producida es una instancia yes si y solo si la instancia de entrada Planar 3SAT es una instancia yes. Dado que esta reducción también es tiempo polinómico (todos los gadgets requieren un espacio polinómico en el tamaño de la instancia de entrada), concluimos que tenemos una reducción válida.