Complexidade parametrizada de P a NP-hard e vice-versa

60

Estou procurando exemplos de problemas parametrizados por um número kN , onde a dureza do problema não é monotônica em k . A maioria dos problemas (na minha experiência) tem uma transição monofásica, por exemplo, k -SAT possui uma transição monofásica de k{1,2} (onde o problema está em P) para k3 (onde o problema é NP- completo). Estou interessado em problemas em que há transições de fase em ambas as direções (de fácil para difícil e vice-versa) à medida que k aumenta.

Minha pergunta é um pouco semelhante à feita em Hardness Jumps in Computational Complexity , e de fato algumas das respostas são relevantes para minha pergunta.

Exemplos que eu conheço:

  1. k -colorability de gráficos planares: em P, exceto quandok=3 , onde está NP-completo.
  2. Árvore de Steiner com terminais k : em P, quando k=2 (cai para o menor caminho s - t ) e quando k=n (cai para MST), mas NP é difícil "no meio". Não sei se essas transições de fase são nítidas (por exemplo, P para k0 mas NP-difícil para k0+1 ). Além disso, as transições de k dependem do tamanho da instância de entrada, diferentemente dos meus outros exemplos.
  3. Contando atribuições satisfatórias de um módulo de fórmula planar n : Em P quando n é um número primo de Mersenne n=2k1 e # P-completo para a maioria (?) / Todos os outros valores de n (de Aaron Sterling neste tópico ) . Muitas transições de fase!
  4. Detecção de subgráfico induzido: o problema não é parametrizado por um número inteiro, mas por um gráfico. Existem gráficos H1H2H3 (onde denota um certo tipo de relação de subgráfico), para o qual determinar se HiG para um dado gráfico G está em P para i{1,3} mas NP- completo para i=2 . (de Hsien-Chih Chang no mesmo tópico ).
mikero
fonte
3
Correção menor, por exemplo (3): o problema está em se n for um número inteiro do tipo Mersenne, ou seja, n = 2 k - 1 para algum número natural k ; n não precisa ser primo. (Por exemplo, 2 11 - 1 não é primo.) A menos que n seja dessa forma, o problema é # P - completo. Pnn=2k1kn2111nP
Aaron Sterling
Obrigado @ Aaron Sterling - revi esse exemplo adequadamente.
Mikero
11
Correção principal no exemplo (3): As fórmulas também precisam ser monótonas, lidas duas vezes e ter cláusulas de tamanho , em que n = 2 k - 1 , para serem tratáveis. Isso foi provado por Jin-Yi Cai e Pinyan Lu. Não é assim que a Valiant o motivou. Ele fixou o tamanho da cláusula em 3 e depois variou apenas o módulo. Era conhecido por ser duro na característica 0. Valiant mostrou dureza mod 2 e tratabilidade mod 7. A dureza mod 2 é P = # 2 dureza P , não # P-dureza. Não sei que família de problemas parametrizada você está tentando descrever. kn=2k1P=#2P
Tyson Williams
11
Para saber mais sobre isso, incluindo as referências em papel, consulte Holographic_algorithm # History na Wikipedia.
Tyson Williams
Uma preocupação relativamente exemplo (4): espero que significa que denotam L ser uma realização da s grafo- H . Mas como podemos dizer que theta prisma pirâmide? Observe que estamos falando de subgráficos induzidos, não subgráficos. HGGsH
Cyriac Antony 25/01

Respostas:

25

Um campo com muita não monotonicidade da complexidade do problema é o teste de propriedades. Seja o conjunto de todos os gráficos n -vertex e chame P G n uma propriedade de gráfico. Um problema genérico é determinar se um gráfico G tem a propriedade P (ou seja, G P ) ou está longe de ter a propriedade P em algum sentido. Dependendo do que P é e que tipo de acesso à consulta você tem no gráfico, o problema pode ser bastante difícil.GnnPGnGPGPPP

Mas é fácil perceber que o problema não é monótono, pois se temos , o fato de P ser facilmente testável não implica que S seja facilmente testável ou que T seja. SPTPST

Para ver esta, é o suficiente para observar que e P = são ambos trivialmente testável, mas que, para algumas propriedades, existem fortes limites inferiores.P=GnP=

Aaron Roth
fonte
Você poderia mencionar (ou apontar para) um exemplo não trivial? Eu acho que você já conhece alguns. Também é interessante saber se há transições de fase P NP P NP.
Cyriac Antony 25/01
20

Para um dado gráfico e um número inteiro k 1 , a k- ésima potência de G , denotada por G k , tem o mesmo conjunto de vértices, de modo que dois vértices distintos são adjacentes em G k se a distância em G for no máximo k . O problema de k- ésima potência do gráfico dividido pergunta se um determinado gráfico é a k- ésima potência de um gráfico dividido.Gk1kGGkGkGkkk

vb le
fonte
17

ΔΔ=23 Δ 6Δ73Δ6

A questão relacionada é discutida aqui .

Oleksandr Bondarenko
fonte
14

Determinando se um gráfico tem uma camarilha dominante para:G

  • diam(G)=1 é trivial - a resposta é sempre 'sim'
  • diam(G)=2 é NP-completo
  • diam(G)=3 é NP-completo
  • diam(G)4 é trivial - a resposta é sempre 'não'

O caso é devido a Brandstädt e Kratsch , e o caso é observado em um artigo recente meu .d i a m ( G ) = 2diam(G)=3diam(G)=2

Austin Buchanan
fonte
+1 boa resposta. O que está dominando a camarilha?
Mohammad Al-Turkistany
11
Assim como parece - um conjunto dominante que também é um clique .
Austin Buchanan
13

Este é um exemplo do fenômeno que você está procurando?

Considere o problema do k-Clique, em que k é o tamanho da camarilha que estamos procurando. Portanto, o problema é "Existe um clique do tamanho k no gráfico G nos n vértices?"

Para todas as constantes k, o problema está em P. (O algoritmo de força bruta é executado no tempo .) Para valores grandes de k, por exemplo valores como n / 2, é NP completo. Quando k se aproxima muito de n, como nc para alguma constante c, o problema está em P novamente, porque podemos pesquisar todos os subconjuntos de n vértices de tamanho nc e verificar se algum deles forma um clique. (Existem apenas desses subconjuntos, que são polinomialmente grandes quando c é uma constante.)O ( n c )O(nk)O(nc)

Robin Kothari
fonte
7
Esse fenômeno ocorre apenas porque podemos ver k como min (k, nk) e resolver o conjunto de k-clique ou k-indept (realmente o mesmo problema). Se pensarmos em 0 <k <= n / 2 por esse motivo, a complexidade está aumentando estritamente em k.
Aaron Roth
4
@ Aaron: Receio que seu argumento não esteja correto. Encontrar um clique do tamanho n-k é muito diferente de encontrar um conjunto independente de tamanho k. Você deve estar confuso pelo fato de que encontrar um clique do tamanho k em um gráfico G é equivalente a encontrar um conjunto independente de tamanho k no complemento de G.
Tsuyoshi Ito
Tsuyoshi: Sim, claro. Eu pretendia dizer que WLOG, você pode assumir que k <= n / 2, pois se não, pegue o gráfico do complemento e resolva o problema para k '= nk. E, claro, isso destaca que a complexidade está aumentando em k.
Aaron Roth
11
@ Aaron: “se não, pegue o gráfico do complemento e resolva o problema para k '= nk.” Essa é exatamente a afirmação incorreta que estou tentando objetar. Deixe-me repetir o que eu disse: “encontrar uma clique do tamanho k em um gráfico G é equivalente a encontrar um conjunto independente de tamanho k no complemento de G.” Encontrar uma clique do tamanho k em um gráfico G não é equivalente a encontrar uma panelinha de tamanho n-k no complemento de G.
Tsuyoshi Ito
2
Ah sim. :-) Isso foi bobagem, retiro minha objeção. O que está acontecendo aqui é apenas Binomial [n, k] = Binomial [n, nk] e, portanto, o tempo de execução da pesquisa exaustiva é monótono aumentando para k <n / 2 e monótono diminuindo para k> n / 2.
Aaron Roth
12

Aqui está um exemplo que pode ser do tipo que você está procurando. O parâmetro não é um número inteiro, é um par de números. (Embora um deles possa ser corrigido para torná-lo um problema de um parâmetro).

O problema é avaliar o polinômio de Tutte de um gráfico G nas coordenadas (x, y). Podemos restringir as coordenadas para serem inteiros. O problema está em P se (x, y) é um dos pontos (1, 1), (-1, -1), (0, -1), (-1,0) ou é satisfatório (x-1 ) (y-1) = 1. Caso contrário, é # P-difícil.

Eu peguei isso no artigo da Wikipedia sobre o polinômio Tutte .

Robin Kothari
fonte
12

E a questão de calcular a permanente de uma matriz módulo ? Para isso é fácil (já que permanente = determinante) e Valiant (em " A complexidade de calcular o permanente ") mostrou que pode ser calculado o módulo no tempo para por uma variante modificada da eliminação gaussiana. Mas para que não é uma potência de , é UP-Hard. k = 2 2 d O ( n 4 d - 3 ) d 2 k 2kk=22dO(n4d3)d2k2

Kevin Costello
fonte
10

Outro problema com esse fenômeno é o problema MÍNIMO -SPANNER em gráficos divididos.t

Para uma constante , um -spanner de um gráfico conectado é um spanning subgráfico conectado de tal que, para cada par de vértices e , a distância entre e em é na maioria vezes a sua distância em . O problema MINIMO -SPANNER solicita uma chave com número mínimo de arestas de um determinado gráfico.t G H G x y x y H t G t tttGHGxyxyHtGtt

Um gráfico dividido é um gráfico cujo conjunto de vértices pode ser particionado em um clique e em um conjunto independente.

No presente documento , foi demonstrado que o mínimo de 2-INGLESA em gráficos de divisão é NP-duro, enquanto para cada , MÍNIMO -SPANNER é fácil de gráficos de divisão.tt3t

user13136
fonte
10

Um exemplo bem conhecido é a coloração edge.k

É decidível em tempo polinomial se caso contrário, ele é completo .N PkΔNP

Para gráficos cúbicos, decidindo a existência de coloração de arestas usando:

  • k=2 cores é trivial, pois a resposta é sempre não.
  • N Pk=3 cores é completoNP
  • k4 cores é trivial, pois a resposta é sempre sim.

Holyer, Ian (1981), "The NP-completeness of edge-colouring", SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Mohammad Al-Turkistany
fonte
Você poderia, por favor, adicionar uma referência?
Oleksandr Bondarenko 27/02
10

Este é um exemplo interessante (e surpreendente) para uma transição de fase P NP-difícil P NP-difícil :

Decidir se um gráfico completo em vértices, no qual cada vértice tem uma classificação estrita de todos os outros vértices, admite que uma correspondência popular seja em P para ímpar e NP-difícil para par . (O parâmetro é o número do vértice .)nnnn

A prova foi anunciada neste artigo .

user13136
fonte
8

Um caminho em um gráfico colorido de borda é arco - íris se nenhuma cor aparecer duas vezes nele. Um gráfico é colorido do arco - íris se houver um caminho do arco-íris entre cada par de vértices. Permita que RAINBOW- -COLORABILITY seja o problema de decidir se um determinado gráfico pode ser colorido em arco-íris usando cores.kkk

Para qualquer gráfico , o problema é fácil para pois é igual a verificar se é um gráfico completo. Para gráficos divididos , o problema é completo para e em para todos os outros valores de .k = 1 G N P k { 2 , 3 } P kGk=1GNPk{2,3}Pk

Veja Chandran, L. Sunil, Deepak Rajendraprasad e Marek Tesař. "Coloração arco-íris de gráficos divididos". pré-impressão do arXiv arXiv: 1404.4478 (2014).

Juho
fonte
6

Um subconjunto de um gráfico é um cutset desconectado se e estiverem desconectados.G G [ U ] G - UUV(G)GG[U]GU

Decidir se um gráfico de diâmetro 1 tem um cutset desconectado é trivial. O problema torna-se NP-difícil nos gráficos de diâmetro 2, veja este artigo e é novamente fácil nos gráficos de diâmetro, pelo menos 3, veja este artigo .

user13136
fonte