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 .
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.
Luego, para una hipergrafía y un mapeo ,
{ }.
Además, deje que el peso ( ) = .
Entonces, una descomposición fraccional de hipertree de es un triple , donde:
- es una descomposición del árbol de , y
- es una familia de asignaciones de a st por cada .
( γ t ) , t ∈ V ( 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 H
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:
¿Se sabe algo sobre la (in) trazabilidad de los CSP sobre gráficos con ancho de hipertree fraccionario ilimitado?
fuente