CSP con ancho de hipertree fraccionario ilimitado

10

En SODA 2006, Martin Grohe y D niel papel de Marx "resolución de restricciones a través de cubiertas de borde fraccional" ( cita ACM ) mostraron que para la clase de hypergraphs H con anchura Hypertree fraccional acotada, CSP ( H ) P T I M E .a´HHPTIME

Definiciones, etc.

Para una gran encuesta de descomposiciones de árbol estándar y ancho de árbol, vea aquí (¡Gracias de antemano, JeffE!).

Deje ser una hipergrafía.H

Luego, para una hipergrafía H y un mapeo γ:E(H)[0,) ,

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

Además, deje que el peso ( γ ) = eEγ(e) .

Entonces, una descomposición fraccional de hipertree de H es un triple (T,(Bt)tV(T),(γt)tV(T)) , donde:

  • (T,(Bt)tV(T)) es una descomposición del árbol deH , y
  • (γt)tV(T) es una familia de asignaciones deE(H) a[0,) st por cadatV(T),BtB(γt) .

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

Finalmente, la anchura Hypertree fraccionada de , FHW ( ), es el mínimo de las anchuras de más de todas las posibles descomposiciones HyperTree fraccionarias de .H HHHH

Pregunta

Como se indicó anteriormente, si el ancho de hipertree fraccional del gráfico subyacente de un CSP está limitado por una constante, entonces hay un algoritmo de tiempo polinómico para resolver el CSP. Sin embargo, se dejó como un problema abierto al final del documento vinculado si había alguna familia de instancias de CSP con tiempo polinómico que tuviera un ancho de hipertree ilimitado. (También debo señalar, esta pregunta se resuelve por completo en el caso del ancho de árbol acotado vs. no acotado ( cita ACM ) bajo el supuesto de que .) Dado que ha pasado algún tiempo desde el primer documento vinculado, Además, soy relativamente inconsciente del estado general de este subcampo, mi pregunta es:FPTW[1]

¿Se sabe algo sobre la (in) trazabilidad de los CSP sobre gráficos con ancho de hipertree fraccionario ilimitado?
Daniel Apon
fuente

Respuestas:

8

Se vinculó a dos documentos, ambos con conjeturas. Supongo que te refieres a la conjetura de Grohe de 2007.

Esta pregunta fue respondida en 2008:

Teorema 5. CSP (C , _) está en NP, pero ni en P ni en NP completo (a menos que P = NP). Además, el conjunto C se puede decidir en tiempo polinomial determinista.000

La idea es hacer agujeros en los tamaños de instancia de CLIQUE, mediante la misma técnica de diagonalización retrasada introducida por Ladner para su teorema. Tenga en cuenta que el conjunto C contiene camarillas arbitrariamente grandes, y el ancho fraccionario de hipertree de una -clique es . Por lo tanto, es posible tener CSP de la forma CSP (A, _) que son de complejidad intermedia, donde A tiene un ancho de hipertree fraccionario ilimitado. Esto responde a la conjetura de Grohe en negativo. n n / 20nn/2

En la misma conferencia, Chen, Thurley y Weyer tenían un artículo con un resultado similar, pero eso requería fuertes incrustaciones, por lo que técnicamente no era la forma correcta para la conjetura.

Finalmente, cualquier clase de instancias de CSP se puede transformar en una representación con el ancho de hipertree fraccionario en el peor de los casos. En muchos casos, esta transformación tiene un tamaño polinomialmente limitado y puede realizarse en tiempo polinómico. Esto significa que es fácil generar CSP con un ancho de hipertree fraccionario ilimitado, incluso una equivalencia homomórfica de módulo. Estos CSP no van a tener la forma CSP (A, _) ya que las estructuras objetivo son especiales, pero proporcionan una buena razón por la cual los CSP definidos al restringir solo las estructuras fuente no son tan interesantes: a menudo es solo es demasiado fácil ocultar la estructura de árbol de una instancia de CSP cambiando la representación para que la estructura de origen tenga un ancho grande. (Esto se discute en el capítulo 7 de mi tesis ).

András Salamon
fuente
Gracias por la gran respuesta. Una pregunta rápida de seguimiento: Mi lectura de "La complejidad del homomorfismo y los problemas de satisfacción de restricciones vistos desde el otro lado" es que existe una dicotomía P vs. NP-c para CSP de la forma CSP (C, _) para no hipergrafías de arity acotada, ¿estoy en lo cierto al creer eso? O más al punto: no hay suposiciones / conjeturas ocultas en el Corolario 6.1 de este documento que desconozco, ¿verdad? O, además, ¿la dicotomía es simplemente P frente a no-P? (Lo siento si esto es obvio.)
Daniel Apon
2
@Daniel: Este documento no se refería tanto a las dicotomías sino a caracterizar con precisión los casos de restricción de estructura manejable como los de ancho limitado. Se sabía que el ancho delimitado implicaba que era manejable, pero la parte clave del papel de Grohe está en la otra dirección. El ancho ilimitado implica incrustar menores de cuadrícula de tamaño arbitrariamente grande, que luego se puede usar para codificar un problema NP-hard como CLIQUE. La conjetura de la dicotomía de Feder / Vardi para CSP es para restricciones de tipo CSP (_, B), que se cree que están en P o NP-completo.
András Salamon
@Daniel: Por cierto, estas cosas ciertamente no fueron obvias para mí la primera vez que las leí. El rápido resumen del artículo de Grohe en mi comentario anterior le debe mucho a Dave Cohen.
András Salamon