Complexidade do Problema de Decisão de Conjunto Independente Comparativo

8

Considere o seguinte problema:

Entrada: (G1, G2) em que G1 e G2 são gráficos não direcionados

Pergunta: O tamanho do conjunto independente máximo de G1 é pelo menos tão grande quanto o tamanho do conjunto independente máximo de G2?

Parece uma pergunta bastante natural, e ainda assim não consegui encontrar uma classe de complexidade para a qual esse problema esteja completo. Alguém sabe disso? Como ponto de partida, é fácil perceber que o problema é difícil de NP e está contido em P com acesso a um oracle NP com muitas consultas de log.

Daniel Grier
fonte
4
Também é co-NP-difícil, de fato, dado um gráfico e um número inteiro , usando um dum com um conjunto independente máximo de tamanho (por exemplo, um caminho de comprimento ), é possível criar uma redução de muitos Problema no NPC " contém um conjunto independente de tamanho ?" e seu complemento (troca e ). k G 2 k 2 k G 1k G 1 G 2G1kG2k2kG1kG1G2
Marzio De Biasi 12/02

Respostas:

2

Esse problema é realmente completo para a classe de máquinas de Turing com tempo polinomial com acesso a um oracle NP com muitas consultas de log (também conhecidas como ). O resultado aparece em um documento de 2000 da FST TCS de Spakowski e Vogel intitulado " : Uma abordagem clássica para novos resultados". A prova apresentada lá e uma prova a que cheguei independentemente, dependem do critério de Wagner ( de Wagner ("SIAM Bounded Query Classes", SIAM Journal on Computing archive Volume 19 Issue 5, Out. 1990). Θ p 2 Θ p 2Θ2pΘ2pΘ2p

Daniel Grier
fonte
1

Parece que seu problema é Turing-completo para a classe . Como mencionado na pergunta, você já sabe que se enquadra nesta classe. Para mostrar a integridade de Turing, pode-se notar que usar um conjunto independente de tamanho para nos permite determinar (usando a tarefa como um oráculo) se o conjunto máximo independente em é . Repetindo isso com a pesquisa binária de , podemos determinar o tamanho do conjunto independente máximo em . lG1G2l1lnexactG2PNP[O(logn])]lG1G2l1lnexactG2

Aplique o acima aos complementos do gráfico para determinar o tamanho exato da camarilha máxima em , em vez do conjunto independente. Depois de determinar o tamanho da camarilha máxima, podemos decidir se é divisível por um determinado número . Em seguida, podemos invocar o resultado de que a decisão de decidir se o tamanho máximo de clique de um gráfico é divisível por um determinado número está completa para ( veja Krentel, "A complexidade dos problemas de otimização", J. of Computer and System Sciences, 36 (1988/3), pp. 490–509, Teorema 3.5) k P N P [ O ( log n ] ) ]G2kPNP[O(logn])]

Enquanto o resultado referenciado de Krentel prova a completude múltipla do problema em , a redução acima mostra apenas a integridade de Turing, já que na busca binária temos que chamar o oracle várias ( ) vezes. lognPNP[O(logn])]logn

Andras Farago
fonte
1
Parece simples a codificação de todas as consultas do NP oracle em instâncias desse problema. Além disso, como esse argumento pode ser repetido com qualquer linguagem NPC, ele não parece revelar nada sobre o poder dessa linguagem.
Daniel Grier
Você está certo, esqueci que o mesmo argumento poderia ser feito usando, por exemplo, o problema mais simples de Conjunto Independente (ou, nesse caso, com qualquer problema de NPC). O que certamente seria mais interessante é mostrar que esse problema do Conjunto Independente Comparativo é um completo para a classe mencionada.
Andras Farago
0

Seu problema é também muitos e um difícil para implicações entre instâncias NP.

Reduza o lado direito da implicação para o conjunto independente de qualquer maneira conveniente e reduza o lado esquerdo da implicação para o conjunto independente, de forma a garantir que o gráfico não possa ter um conjunto independente maior que o tamanho do destino. (Por exemplo, reduza para CNF-SAT e aplique essa redução apesar de ter uma instância geral de CNF-SAT, em vez de necessariamente uma instância de 3-SAT.) Adicione um número de vértices isolados iguais à diferença entre os tamanhos de destino para o tamanho de destino da instância menor e aumente o tamanho do destino no mesmo número. Isso obviamente fornece uma instância equivalente e torna os tamanhos de destino resultantes iguais.

Se o tamanho do destino for zero, retorne a instância vazia do seu problema, caso
contrário , adicione [tamanho do destino menos um] vértices isolados ao gráfico correspondente à instância no
lado direito da implicação e conecte cada um deles a todos os vértices que estavam lá
antes desta frase e retornam com G1 igual ao gráfico e G2 igual ao outro gráfico.

(Além disso, suas instâncias de problemas podem ser trivialmente
reduzidas a conjunções de implicações entre instâncias de NP.)


fonte