Dureza NP de uma especialização Set Cover

O seguinte problema é NP-difícil?

Dado um conjunto de números reais (metas) e um "tridente" definido por duas distâncias , do centro do tridente, qual é o número mínimo de posições de o tridente para cobrir todos os alvos, por exemplo, x 1 , … , x N a b K p 1 , … , p K K ⋃ k = 1 { p k - a , p k , p k + b } ⊇ { x 1 , … , x N } $N$$x_1,\dotsc,x_N$$a$$b$$K$$p_1,\dotsc,p_K$

Obviamente, este é um caso especial do problema da tampa do conjunto : Considerando todos os conjuntos , com representando todas as posições potenciais "relevantes", procuramos o número mínimo de conjuntos que cobrem o universo . De maneira equivalente, podemos representar o problema como um gráfico bipartido de nós de posição e alvo e considerar o problema do conjunto de ocorrências .p k ∈ { x n + t ∣ n ∈ { 1 , … , N } , t ∈ { a , 0 , - b } } { x 1 , … , x N$\{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\}\}$$\{x_1,\dotsc,x_N\}$

Observe que o problema não é difícil de NP se o tridente perder um de seus "entalhes": cada alvo pode ser coberto de 2 posições e cada posição cobre no máximo 2 alvos; portanto, o gráfico bipartido correspondente de posições e alvos potenciais é um união de caminhos. Em cada caminho, é fácil determinar um conjunto de batidas mínimo (ou seja, os nós de posição interna).

Mas o caso tridente é difícil?

Visão geral

Esse problema é difícil de NP; mais precisamente, o problema de decisão associado (em que nos perguntar se um alvo número de tridentes pode cobrir todo o dado x i s) é NP-hard. Vamos nos referir a esse problema de decisão como o Problema Numérico de Cobertura de Tridentes.$k$$x_i$

Para provar que o problema de cobertura numérica do tridente é difícil de NP, apresentamos o seguinte problema intermediário, que chamaremos de problema de cobertura do triângulo de grade:

Entrada : Um conjunto finito de pares de coordenadas inteiros e um valor inteiro k .$S \subset \mathbb{Z}^+ \times \mathbb{Z}^+$$k$

Saída : Sim ou não, com uma saída sim, se e somente se existir um conjunto com | T | ≤ k tal que S ⊆ ⋃ ( x , y ) ∈ T { ( x , y ) , ( x , y + 1 ) , ( x + 1 , y ) $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)\}$

Pensando graficamente sobre este problema, recebemos um subconjunto da rede inteira e pedimos para cobrir todos os pontos desse subconjunto com comprimento lateral- ( 1 , 1 , $k$triângulos retângulos em uma orientação específica (em particular, esses triângulos devem ter vértices na forma(x,y),(x,y+1)e(x+1,y)). Somos convidados a dizer sim, se e somente se isso for possível.$(1, 1, \sqrt{2})$$(x, y)$$(x, y+1)$$(x+1, y)$

Para mostrar que a cobertura numérica do tridente é NP-difícil, fornecemos duas reduções: uma redução da cobertura planar 3SAT para a grade do triângulo e uma redução da cobertura do triângulo da grade para a cobertura numérica do tridente. Juntos, eles se transformam em uma redução do problema NP-difícil Planar 3SAT para o problema da Capa Numérica de Tridente, o que implica que a Capa Numérica de Tridente é NP-difícil.

Observe que, como estamos usando números reais no problema de cobertura numérica do tridente, a questão da codificação e do tamanho da entrada deve surgir. Evitamos esse problema sempre usando números no formato em nossas instâncias de cobertura numérica de tridente, permitindo uma codificação eficiente simplesmente codificandop+q$p + q\sqrt{2}$$p + q\sqrt{2}$$(p, q)$

Redução 1: da cobertura do triângulo da grade à cobertura numérica do tridente.

$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$

Essa redução é claramente uma operação de tempo polinomial; portanto, a única coisa que resta a mostrar é que a redução é a preservação da resposta.

$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})$

Redução 2: do Planar 3SAT para a cobertura do triângulo da grade.

Para essa redução, recebemos uma instância 3SAT na forma de um gráfico bipartido planar. Os vértices de uma parte correspondem a variáveis ​​e os vértices da outra parte, cada um do grau 3, correspondem a cláusulas. Cada aresta é rotulada como positiva ou negativa, indicando de que maneira a variável é incluída na cláusula (positiva ou negativamente).

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

Primeiro, descrevemos um fio. Um fio consiste em uma sequência de um número ímpar de pontos (na rede inteira) onde o primeiro e o último são chamados terminais, de modo que cada par consecutivo possa ser coberto por um triângulo, sem que o triângulo atinja qualquer outro ponto do fio. Como exemplo, considere o seguinte fio:

xoo       x
   o       o
   o ooo   o
   o o  oooo
    oo

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

Aqui, mostramos as duas maneiras de cobrir o exemplo de cima (onde dois pontos são rotulados com o mesmo número se forem cobertos pelo mesmo triângulo):

x11       9
   2       9
   2 556   8
   3 4  6778
    34

ou

112       x
   2       9
   3 566   9
   3 5  7788
    44

Uma preocupação é que podemos desejar conectar dois terminais com um fio, mas não podemos fazê-lo, porque qualquer "fio" entre esses dois terminais teria comprimento uniforme. No entanto, esse não é o caso: sempre podemos escolher uma rota para um fio para que esse fio tenha um comprimento ímpar (e, portanto, seja um fio válido). Substituir qualquer segmento horizontal do fio de comprimento 6 pelo seguinte segmento de 7 fios pode fixar a paridade do comprimento do fio:

oo  oo
  ooo 

A seguir, apresentamos um gadget de cláusula. Uma cláusula simplesmente conecta um dos terminais de três fios de forma que, se um dos fios for satisfeito para que o terminal compartilhado seja coberto, o triângulo que cobre esse terminal compartilhado não cobre nenhum ponto dos outros fios:

      o
      o
      o
   ooox
       ooo

Para que o terminal compartilhado seja coberto, pelo menos um dos três fios deve satisfazer de tal forma que os triângulos que satisfazem o fio não cubram o terminal não compartilhado dos fios.

Por fim, apresentamos o gadget variável. O gadget variável é um loop em forma de fio grande (de comprimento uniforme) com terminais ocorrendo opcionalmente para o lado a cada três linhas, da seguinte maneira:

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

A variável pode crescer verticalmente para acomodar o número necessário de terminais. Os terminais nas linhas de paridade par correspondem a ocorrências positivas da variável e os nas linhas de paridade ímpar correspondem a ocorrências negativas. Assim como no fio, os pontos não terminais do dispositivo variável podem ser satisfeitos usando o número mínimo de triângulos (metade do número de pontos no loop) de exatamente duas maneiras. Essas duas configurações abrangem todos os terminais de ocorrência positiva ou todos os terminais de ocorrência negativa do dispositivo variável.

Juntar tudo é bastante óbvio: construímos o gráfico bipartido usando dispositivos variáveis, dispositivos de cláusula (terminais compartilhados) e fios que conectam os terminais. O número total de triângulos necessário para cobrir os pontos não terminais dos fios e variáveis ​​é então o número alvo de triângulos.

Claramente, não podemos cobrir toda a grade com menos do que triângulos. Além disso, podemos ter certeza de que os pontos não terminais são cobertos, uma vez que as variáveis ​​e os fios serão satisfeitos de uma das duas maneiras descritas. Portanto, a única tarefa é satisfazer os terminais.

Em cada variável, todos os terminais de ocorrência positivos ou negativos serão satisfeitos pelo dispositivo variável. Os outros terminais do dispositivo precisam ser satisfeitos com os fios conectados. Os terminais da cláusula poderão ser satisfeitos se, e somente se, todas as cláusulas estiverem conectadas a pelo menos um fio cujo outro terminal ainda não o utilizou (um fio cujo outro terminal foi satisfeito pelo seu dispositivo variável conectado). Em outras palavras, todos os terminais estão satisfeitos se, e somente se, a atribuição de variáveis ​​de acordo com as configurações dos dispositivos variáveis ​​satisfizer todas as cláusulas.

Como você pode ver, a instância Grid Triangle Cover produzida é uma instância yes se e somente se a instância Planar 3SAT de entrada for uma instância yes. Como essa redução também é tempo polinomial (todos os dispositivos requerem polinômio de espaço no tamanho da instância de entrada), concluímos que temos uma redução válida.