CSPs com largura de hiperárvore fracionária ilimitada

10

No SODA 2006, Martin Grohe e D niel papel de Marx "Constraint solução através de tampas de borda fraccionada" ( citação ACM ) mostrou que, para a classe de Hipergrafos H com largura hypertree fraccionada limitada, CSP ( H ) P T I M E .a´HHPTIME

Definições, etc.

Para uma grande pesquisa sobre decomposições de árvores e largura de árvore padrão, consulte aqui (Agradecemos antecipadamente, JeffE!).

Seja um hipergrafo.H

Então, para um hipergrafo H e um mapeamento γ:E(H)[0,) ,

B(γ)= {vV(H):eV(H),veγ(e)1 }.

Além disso, deixe o peso ( γ ) = eEγ(e) .

Em seguida, uma decomposição fracionada de hiperárvore de H é uma tripla (T,(Bt)tV(T),(γt)tV(T)) , onde:

  • (T,(Bt)tV(T)) é uma decomposição em árvore deH , e
  • (γt)tV(T) é uma família de mapeamentos deE(H) de[0,) r para cadatV(T),BtB(γt) .

(T,(Bt)tV(T),(γt)tV(T))max(γt),tV(T)

Finalmente, a largura hypertree fraccionada de , FHW ( ), é o mínimo das larguras mais de todos os possíveis decomposições hypertree fraccionais de .HHH

Questão

Como afirmado acima, se a largura fracionada da hiperárvore do gráfico subjacente de um CSP estiver limitada por uma constante, existe um algoritmo de tempo polinomial para resolver o CSP. No entanto, ficou como um problema em aberto no final do artigo vinculado se havia famílias solucionáveis ​​em tempo polinomial de instâncias de CSP com largura de hiperárvore ilimitada. (Devo também salientar que esta questão está completamente resolvida no caso de largura de árvore limitada vs. ilimitada ( citação ACM ) sob a suposição de que .) Como já faz algum tempo desde o primeiro artigo vinculado, Além disso, estou relativamente inconsciente do estado geral desse subcampo, minha pergunta é:FPTW[1]

Existe algo conhecido sobre a (in) tratabilidade de CSPs sobre gráficos com largura fracionada ilimitada de hiperárvore?
Daniel Apon
fonte

Respostas:

8

Você vinculou dois documentos, ambos com conjecturas. Presumo que você esteja falando da conjectura de Grohe em 2007.

Esta pergunta foi respondida em 2008:

Teorema 5. CSP (C , _) está em NP, mas nem em P nem em NP completo (a menos que P = NP). Além disso, o conjunto C pode ser decidido em tempo polinomial determinístico.00

A idéia é abrir buracos nos tamanhos de instância do CLIQUE, pela mesma técnica de diagonalização atrasada introduzida por Ladner para seu teorema. Observe que o conjunto C contém cliques arbitrariamente grandes e a largura fracionada da hiperárvore de uma -clique é . Portanto, é possível ter CSPs do formato CSP (A, _) que são de complexidade intermediária, em que A possui largura fracionada ilimitada de hiperárvore. Isso responde à conjectura de Grohe no negativo.0nn/2

Na mesma conferência, Chen, Thurley e Weyer tiveram um artigo com um resultado semelhante, mas isso exigiu fortes embeddings, de modo que tecnicamente não era a forma correta para a conjectura.

Finalmente, qualquer classe de instâncias de CSP pode ser transformada em uma representação com a largura de hiperárvore fracionária do pior caso. Em muitos casos, essa transformação é polinomialmente delimitada em tamanho e pode ser feita em tempo polinomial. Isso significa que é fácil gerar CSPs com largura de hiperárvore fracionária ilimitada, mesmo equivalência homomórfica no módulo. Esses CSPs não terão o formato CSP (A, _), pois as estruturas de destino são especiais, mas fornecem uma boa razão para que os CSPs definidos restringindo apenas as estruturas de origem não sejam tão interessantes: geralmente é apenas É muito fácil ocultar a estrutura em forma de árvore de uma instância do CSP alterando a representação para que a estrutura de origem tenha grande largura. (Isso é discutido no capítulo 7 da minha tese .)

András Salamon
fonte
obrigado pela ótima resposta. Uma pergunta rápida de acompanhamento: Minha leitura de "A complexidade do homomorfismo e os problemas de satisfação com as restrições vistas do outro lado" é que existe uma dicotomia P vs. NP-c para CSPs da forma CSP (C, _) para não-hipergrafos de aridade limitada, estou certo em acreditar nisso? Ou, mais precisamente - não há nenhuma suposição / conjectura oculta no Corolário 6.1 deste artigo que eu desconheço, existe? Ou ainda, a dicotomia lá é simplesmente P vs. não-P? (Desculpe se isso é óbvio.)
Daniel Apon
2
@ Daniel: Este artigo não tratava tanto de dicotomias, mas de caracterizar com precisão os casos restritos à estrutura tratável como aqueles de largura limitada. Sabe-se que a largura delimitada implica em tratável, mas a parte principal do papel de Grohe está na outra direção. A largura não vinculada implica incorporar menores da grade de tamanho arbitrariamente grande, que podem ser usados ​​para codificar um problema difícil de NP como CLIQUE. A conjectura de dicotomia Feder / Vardi para CSPs é para restrições do tipo CSP (_, B), que se acredita estarem em P ou NP-completas.
András Salamon
@ Daniel: A propósito, essas coisas certamente não foram óbvias para mim na primeira vez que as li. O breve resumo do artigo de Grohe no meu comentário anterior deve muito a Dave Cohen.
András Salamon