Método de descomposición (satisfacción de restricciones)

En teoría de grafos , un vértice separador es un nodo que, al ser eliminado, "rompe" el grafo. Formalmente, es un nodo cuya eliminación aumenta el número de sus componentes conexas. Una componente biconexa de un grafo es un conjunto máximo de sus nodos cuyo subgrafo inducido es conexo y no tiene ningún vértice separador. Se sabe, por la teoría de grafos, que las componentes biconexas y los vértices separadores de un grafo forman un árbol. Este árbol se puede construir de la siguiente manera: sus nodos son las componentes biconexas y los vértices separadores del grafo; las aristas solo conectan una componente biconexa con un vértice separador, y en particular, esto ocurre si el vértice está contenido en la componente. Se puede demostrar que este grafo es, de hecho, un árbol.

Si las restricciones de un problema de satisfacción de restricciones binarias se consideran como aristas de un grafo cuyos nodos son las variables, este árbol constituye una descomposición del problema. El ancho de una descomposición es el número máximo de vértices en un componente biconexo.

El método de descomposición cíclica divide un problema en una parte cíclica y otra acíclica. Si bien no se ajusta a la definición de los otros métodos de descomposición, que generan un árbol cuyos nodos están etiquetados con conjuntos de nodos, puede reformularse fácilmente en esos términos.

Este método de descomposición se basa en la idea de que, una vez asignadas ciertas variables, el problema resultante tras su eliminación puede ser acíclico. Formalmente, un conjunto de corte cíclico de un grafo es un conjunto de nodos que, al eliminarlos, lo convierte en acíclico. Se puede aplicar una definición similar a un problema de satisfacción de restricciones utilizando su grafo primal. La anchura de una descomposición cíclica es el número de variables en el conjunto de corte. La anchura de un problema es la anchura mínima de sus descomposiciones de conjuntos de corte cíclicos.

Esta descomposición no se ajusta al esquema de las demás descomposiciones, ya que el resultado no es un árbol, sino un conjunto de variables (las del conjunto de corte) y un árbol (formado por las variables que no pertenecen a dicho conjunto). Sin embargo, se puede obtener un árbol similar a los generados por los otros métodos de descomposición a partir del árbol resultante de eliminar el conjunto de corte. Esto se logra eligiendo una raíz, añadiendo todas las variables del conjunto de corte a todos sus nodos y las variables de cada nodo a todos sus hijos. El resultado es un árbol cuyo número máximo de variables asociadas a un nodo es igual al tamaño del conjunto de corte más dos. Además de esta suma de dos, este valor corresponde a la amplitud de la descomposición, que se define como el número de variables del conjunto de corte considerado.

Desafortunadamente, determinar el conjunto mínimo a eliminar es un problema NP-difícil .

La descomposición en árbol es un concepto bien conocido de la teoría de grafos. Reformulada en términos de restricciones binarias, una descomposición en árbol consiste en un árbol cuyos nodos están asociados a conjuntos de variables; el alcance de cada restricción está contenido en el conjunto de variables de algún nodo, y el subárbol de nodos asociado a cada variable está conectado. Esta es la forma más general de descomposición para restricciones binarias que sigue el esquema descrito anteriormente, ya que las condiciones impuestas al árbol son solo las necesarias para garantizar la equivalencia entre el problema original y el nuevo.

El ancho de dicha descomposición es el número máximo de variables asociadas al mismo nodo menos uno. El ancho de árbol de un problema es el ancho mínimo de sus descomposiciones de árbol.

La eliminación de cubetas puede reformularse como un algoritmo que trabaja sobre una descomposición de árbol particular. En particular, dada una ordenación de las variables, a cada variable se le asocia una cubeta que contiene todas las restricciones tales que la variable es la mayor en su ámbito. La eliminación de cubetas corresponde a la descomposición de árbol que tiene un nodo para cada cubeta. A este nodo se le asocian todas sus restricciones y corresponde al conjunto de todas las variables de estas restricciones. El padre de un nodo asociado a la cubeta de${\displaystyle x_{i}}$es el nodo asociado al cubo de${\displaystyle x_{j}}$, dónde${\displaystyle x_{j}}$es el nodo más grande que está en una restricción con${\displaystyle x_{i}}$y precede${\displaystyle x_{i}}$en el pedido.

La descomposición biconectada de un problema de satisfacción de restricciones arbitrarias es la descomposición biconectada de su grafo primal. Cada restricción puede aplicarse a un nodo del árbol porque cada restricción crea una camarilla en sus variables sobre el grafo primal, y una camarilla es un componente biconectado o un subconjunto de un componente biconectado.

La descomposición en árbol de un problema de satisfacción de restricciones arbitrarias es la descomposición en árbol de su grafo primal. Cada restricción puede aplicarse a un nodo del árbol porque cada restricción crea una camarilla en sus variables sobre el grafo primal y, para cada descomposición en árbol, las variables de una camarilla están completamente contenidas en las variables de algún nodo.

Este es el mismo método de corte cíclico que utiliza la definición de corte para hipergrafos: un hipercorte cíclico de un hipergrafo es un conjunto de aristas (en lugar de vértices) que hace que el hipergrafo sea acíclico cuando se eliminan todos sus vértices. Se puede obtener una descomposición agrupando todas las variables de un hipercorte en una sola. Esto da como resultado un árbol cuyos nodos son conjuntos de hiperaristas. El ancho de dicha descomposición es el tamaño máximo de los conjuntos asociados a los nodos, que es uno si el problema original es acíclico y el tamaño de su hipercorte mínimo en caso contrario. El ancho de un problema es el ancho mínimo de sus descomposiciones.

Una bisagra es un subconjunto de nodos de un hipergrafo que posee ciertas propiedades definidas a continuación. Una descomposición de bisagra se basa en los conjuntos de variables que son bisagras mínimas del hipergrafo cuyos nodos son las variables del problema de satisfacción de restricciones y cuyas hiperaristas son los ámbitos de dichas restricciones.

La definición de bisagra es la siguiente. Sea${\displaystyle H}$ser un conjunto de hiperaristas. Un camino con respecto a${\displaystyle H}$es una secuencia de aristas tal que la intersección de cada una con la siguiente no es vacía y no está contenida en los nodos de${\displaystyle H}$. Un conjunto de aristas está conectado con respecto a${\displaystyle H}$si, para cada par de sus aristas, existe un camino con respecto a${\displaystyle H}$de los cuales los dos nodos son la primera y la última arista. Un componente conectado con respecto a${\displaystyle H}$es un conjunto máximo de aristas conectadas con respecto a${\displaystyle H}$.

Las bisagras se definen para hipergrafos reducidos, que son hipergrafos donde ninguna hiperarista está contenida en otro. Un conjunto de al menos dos aristas${\displaystyle H}$es una bisagra si, para cada componente conectado${\displaystyle F}$con respecto a${\displaystyle H}$, todos los nodos en${\displaystyle F}$que también están en${\displaystyle H}$están todos contenidos en un único borde de${\displaystyle H}$.

Una descomposición de bisagra se basa en la correspondencia entre problemas de satisfacción de restricciones e hipergrafos. El hipergrafo asociado a un problema tiene como nodos las variables del problema y como hiperaristas los ámbitos de las restricciones. Una descomposición de bisagra de un problema de satisfacción de restricciones es un árbol cuyos nodos son bisagras mínimas del hipergrafo asociado al problema y que cumplen ciertas condiciones. Debido a la correspondencia entre problemas e hipergrafos, una bisagra es un conjunto de ámbitos de restricciones y, por lo tanto, puede considerarse como un conjunto de restricciones. La definición de una descomposición de bisagra requiere tres condiciones adicionales, de las cuales las dos primeras garantizan la equivalencia del problema original con el nuevo. Estas dos condiciones son: el ámbito de cada restricción está contenido en al menos un nodo del árbol, y el subárbol inducido por una variable del problema original está conectado. La condición adicional es que, si dos nodos se unen, comparten exactamente una restricción, y el ámbito de esta restricción contiene todas las variables compartidas por ambos nodos.

El número máximo de restricciones de un nodo es el mismo para todas las descomposiciones de bisagra del mismo problema. Este número se denomina grado de ciclicidad del problema o ancho de bisagra.

La agrupación en árbol o agrupación en árbol de unión se basa en la fusión de restricciones de tal manera que el problema resultante tenga un árbol de unión , este árbol de unión es el resultado de la descomposición.

Un árbol de unión en un problema de satisfacción de restricciones es un árbol en el que cada nodo está asociado a una restricción (y viceversa), y de tal manera que el subárbol de nodos cuya restricción contiene una variable está conectado. Por lo tanto, la creación de un árbol de unión puede considerarse una forma particular de descomposición, donde cada nodo del árbol está asociado al alcance de una restricción.

No todos los problemas de satisfacción de restricciones poseen un árbol de unión. Sin embargo, es posible modificarlos para obtenerlo mediante la fusión de restricciones. La agrupación de árboles se basa en el hecho de que un problema posee un árbol de unión si y solo si su grafo primal es cordal y conforme al problema, lo que significa que las variables de cada clique maximal del grafo primal son el alcance de una restricción y viceversa. La agrupación de árboles modifica un problema arbitrario de tal manera que se cumplan estas dos condiciones. La cordalidad se impone mediante la adición de nuevas restricciones binarias. La conformidad se obtiene mediante la fusión de restricciones.

En particular, la cordalidad se impone añadiendo restricciones binarias "ficticias" al problema. Estas restricciones binarias se satisfacen con cualquier par de valores y se utilizan únicamente para añadir aristas al grafo primal del problema. En concreto, la cordalidad se obtiene añadiendo aristas que generan el grafo inducido del grafo primal según un orden arbitrario. Este procedimiento es correcto porque el grafo inducido siempre es cordal y se obtiene añadiendo aristas al grafo original.

La conformidad requiere que las cliques maximales del grafo primal coincidan exactamente con el alcance de las restricciones. Si bien el alcance de cada restricción original es una clique en el grafo primal, esta clique no es necesariamente maximal. Además, incluso si inicialmente lo era, imponer la cordalidad puede crear una clique mayor. La conformidad se impone mediante la fusión de restricciones. En particular, para cada clique maximal del grafo resultante de imponer la cordalidad, se crea una nueva restricción con la clique como alcance. Los valores que satisfacen esta nueva restricción son aquellos que satisfacen todas las restricciones originales cuyo alcance está contenido en la clique. Mediante esta transformación, cada restricción original queda "incluida" en al menos una nueva restricción. De hecho, el alcance de cada restricción original es una clique del grafo primal. Esta clique permanece como tal incluso después de imponer la cordalidad, ya que este proceso solo introduce nuevas aristas. Como resultado, esta clique es maximal o está contenida en una clique maximal.

Esta traducción requiere la identificación de las camarillas máximas de un grafo cordal. Sin embargo, esto se puede lograr fácilmente utilizando el mismo ordenamiento empleado para garantizar la cordalidad. Dado que los padres de cada nodo están todos conectados entre sí, las camarillas máximas se componen de un nodo (el nodo máximo de la camarilla en un ordenamiento de cardinalidad máxima) y todos sus padres. En consecuencia, estas camarillas máximas se pueden detectar considerando cada nodo junto con sus padres.

El problema resultante de este proceso tiene un árbol de unión, y dicho árbol de unión se puede obtener utilizando nuevamente el mismo ordenamiento de variables. Procediendo desde el último nodo hasta el primero, cada restricción se conecta con la restricción precedente que comparte más variables con ella. La agrupación en árbol de unión puede considerarse un método de descomposición en el que:

• Los elementos de la portada son las camarillas del gráfico resultantes de imponer la cordalidad;
• El árbol es el árbol de unión;
• Cada restricción se asigna a todos los nodos del árbol cuyos conjuntos de variables contienen el alcance de la restricción.

El ancho de una descomposición en agrupamiento de árboles es el número máximo de variables asociadas a cada nodo del árbol. El ancho de un problema es el ancho mínimo de sus descomposiciones en agrupamiento de árboles.

El resultado de la descomposición de bisagras se puede simplificar aún más descomponiendo cada bisagra mediante agrupamiento de árboles. En otras palabras, una vez identificadas las bisagras, se genera un agrupamiento de árboles para cada una de ellas. En términos del árbol resultante, cada nodo se reemplaza por un árbol.

La descomposición de consultas asocia un conjunto de variables y un conjunto de restricciones a cada nodo de un árbol; cada restricción se asocia a un nodo, y el subárbol resultante de los nodos asociados a una variable o restricción dada se conecta. Más precisamente, para cada variable, se conecta el subárbol de nodos asociados a dicha variable o a una restricción que la incluya en su ámbito. El ancho de una descomposición es el número máximo combinado de variables y restricciones asociadas a un nodo.

Asociar restricciones a los nodos posiblemente reduce la amplitud de las descomposiciones y de las instancias. Por otro lado, esta definición de amplitud permite resolver problemas de amplitud fija en tiempo polinomial si se conoce la descomposición. En este caso, el dominio de una nueva variable se obtiene resolviendo un subproblema que puede ser polinomialmente grande, pero que tiene un número fijo de restricciones. Como resultado, se garantiza que este dominio sea de tamaño polinomial; las restricciones del nuevo problema, al ser igualdades de dos dominios, también son de tamaño polinomial.

Una descomposición de consulta pura es aquella en la que los nodos solo están asociados a restricciones. A partir de una descomposición de consulta de un ancho determinado, se puede construir en espacio logarítmico una descomposición de consulta pura del mismo ancho. Esto se logra reemplazando las variables de un nodo que no están presentes en sus restricciones por restricciones que sí las contienen.

Una desventaja de este método de descomposición es que comprobar si una instancia tiene un ancho fijo es, en general, NP-completo ; se ha demostrado que esto ocurre con un ancho de 4.

Una descomposición en hiperárbol asocia un conjunto de variables y un conjunto de restricciones a cada nodo de un árbol. Extiende la descomposición en consultas al permitir que las restricciones de un nodo contengan variables que no se utilizan al crear el dominio de la nueva variable asociada con el nodo. Además de las condiciones comunes para un método de descomposición (el alcance de cada restricción está en al menos un conjunto de variables asociadas con un nodo y el subárbol inducido por una variable original está conectado), se requieren las dos condiciones siguientes:

1. Cada variable original en un nodo está dentro del alcance de al menos una restricción asociada con el nodo;
2. Las variables de las restricciones de un nodo que no son variables del nodo no aparecen en el subárbol con raíz en el nodo.

El ancho de una descomposición en árbol es el número máximo de restricciones asociadas a cada nodo. Si este ancho está limitado por una constante, se puede construir un problema equivalente al original en tiempo polinomial. Las variables que no están asociadas a un nodo, pero que se encuentran dentro del ámbito de las restricciones del nodo, se "proyectan" al construir esta instancia. Esto se puede hacer proyectando primero las restricciones sobre las variables del nodo y luego encontrando todas las soluciones para este subproblema, o bien resolviendo primero el subproblema con todas las restricciones y luego eliminando las variables sobrantes.

Los dos requisitos anteriores no son necesarios para garantizar la equivalencia entre el problema original y el nuevo. Son necesarios para garantizar que los problemas de ancho limitado puedan resolverse en tiempo polinomial.

La posibilidad de asociar una restricción con un nodo mientras algunas de sus variables no están efectivamente asociadas con el nodo puede producir un ancho menor que el ancho de la consulta. Por ejemplo, si un nodo está asociado a${\displaystyle \{C(a,b),c,d,e\}}$en una descomposición de consulta y una restricción${\displaystyle D(c,d,e,f)}$Si existe, una descomposición en hiperárbol puede asociar el mismo nodo con restricciones.${\displaystyle \{C,D\}}$y variables${\displaystyle \{a,b,c,d,e\}}$Dado que al verificar el ancho solo se calculan las restricciones, este nodo tiene un ancho de dos. El mismo nodo tiene un ancho de cuatro al usar la descomposición de consultas (una restricción y tres variables). Esta reducción de ancho es posible si dos o más variables se pueden reemplazar con una sola restricción, incluso si esta restricción contiene una variable que no está asociada con el nodo.

Las descomposiciones generalizadas de hiperárboles se definen como las descomposiciones de hiperárboles, pero se omite el último requisito: la condición de que "las variables de las restricciones de un nodo que no son variables del nodo no aparecen en el subárbol con raíz en dicho nodo". Un problema puede resolverse claramente en tiempo polinomial si se conoce su descomposición de ancho fijo. Sin embargo, no se sabe si la restricción a un ancho fijo es tratable, ya que la complejidad de encontrar una descomposición de ancho fijo, incluso si se sabe que existe, es desconocida ( a fecha de 2001)..

El algoritmo para resolver un problema a partir de un árbol de descomposición incluye dos operaciones: resolver un subproblema relativo a un nodo y crear la restricción relativa a las variables compartidas (el separador) entre dos nodos. Se pueden utilizar diferentes estrategias para estas dos operaciones. En particular, la creación de restricciones en los separadores se puede realizar mediante la eliminación de variables , que es una forma de inferencia, mientras que los subproblemas se pueden resolver mediante búsqueda (retroceso, etc.).

Un problema de este algoritmo es que las restricciones que se transmiten entre nodos pueden tener un tamaño exponencial con respecto al tamaño del separador. La memoria necesaria para almacenar estas restricciones se puede reducir utilizando una descomposición en árbol con separadores pequeños. Sin embargo, estos árboles de descomposición pueden tener un ancho (número de nodos en cada nodo) mayor que el óptimo.

Para un árbol de descomposición dado, se puede imponer un tamaño máximo de separador fijo uniendo todos los pares de nodos cuyo separador sea mayor que dicho tamaño. La fusión de dos nodos generalmente produce un nodo con un conjunto de variables asociadas mayor que el de los dos nodos originales. Esto puede aumentar el ancho del árbol. Sin embargo, esta fusión no modifica los separadores del árbol, salvo por la eliminación del separador entre los dos nodos fusionados.

Esto último es consecuencia de la aciclicidad: dos nodos unidos no pueden unirse al mismo otro nodo. Si${\displaystyle n_{1}}$y${\displaystyle n_{2}}$son dos nodos que se fusionarán y${\displaystyle N_{1}}$y${\displaystyle N_{2}}$son los conjuntos de nodos unidos a ellos, entonces${\displaystyle N_{1}\cap N_{2}=\emptyset }$, ya que de lo contrario habría un ciclo en el árbol. Como resultado, el nodo obtenido al fusionar${\displaystyle n_{1}}$y${\displaystyle n_{2}}$se unirá a cada uno de los nodos de${\displaystyle N_{1}\cup N_{2}}$Como resultado, los separadores de este nodo fusionado son exactamente los separadores de los dos nodos originales.

Como resultado, la fusión de un par de nodos unidos por un separador no modifica los demás separadores. Por lo tanto, se puede imponer un tamaño máximo fijo para los separadores calculando primero todos los tamaños y luego fusionando iterativamente cualquier par de nodos cuyo separador sea mayor que un valor determinado, sin necesidad de recalcular el tamaño de los separadores durante la ejecución.