El problema dual es una reformulación de un problema de satisfacción de restricciones que expresa cada restricción del problema original como una variable. Los problemas duales solo contienen restricciones binarias y, por lo tanto, se pueden resolver mediante algoritmos diseñados para tales problemas. Los gráficos de unión y los árboles de unión de un problema de satisfacción de restricciones son gráficos que representan su problema dual o un problema obtenido a partir del problema dual eliminando algunas restricciones redundantes.
El problema dual de un problema de satisfacción de restricciones contiene una variable para cada restricción del problema original. Sus dominios y restricciones están construidos de manera que se imponga una especie de equivalencia con el problema original. En particular, el dominio de una variable del problema dual contiene un elemento para cada tupla que satisface la restricción original correspondiente. De esta manera, una variable dual puede tomar un valor si y solo si la restricción original correspondiente es satisfecha por la tupla correspondiente.
Las restricciones del problema dual prohíben que dos variables duales tomen valores que correspondan a dos tuplas incompatibles. Sin estas restricciones, una variable dual puede tomar el valor correspondiente a la tupla mientras que otra variable dual toma el valor correspondiente a , lo que asigna un valor diferente a .
En términos más generales, las restricciones del problema dual imponen los mismos valores para todas las variables compartidas por dos restricciones. Si dos variables duales corresponden a restricciones que comparten algunas variables, el problema dual contiene una restricción entre ellas, que impone la igualdad de todas las variables compartidas.
En el problema dual, todas las restricciones son binarias. Todas imponen que dos valores, que son tuplas, coincidan en una o más variables originales.
El gráfico dual es una representación de cómo se restringen las variables en el problema dual. Más precisamente, el gráfico dual contiene un nodo para cada variable dual y un borde para cada restricción entre ellas. Además, el borde entre dos variables está etiquetado por las variables originales que se imponen como iguales entre estas dos variables duales.
El gráfico dual se puede construir directamente a partir del problema original: contiene un vértice para cada restricción y un borde entre cada dos restricciones que comparten variables; dicho borde está etiquetado por estas variables compartidas.
En el gráfico dual, algunas restricciones pueden ser innecesarias. De hecho, las restricciones duales imponen la igualdad de las variables originales, y algunas restricciones pueden ser redundantes debido a la transitividad de la igualdad. Por ejemplo, si y están unidas por una arista cuya etiqueta contiene , y también lo están y , se garantiza la igualdad de en las tres variables duales. Como resultado, una restricción dual entre y que imponga la igualdad de no es necesaria, y podría eliminarse si estuviera presente.
Un grafo obtenido a partir del grafo dual eliminando algunas aristas redundantes se denomina grafo de unión . Si es un árbol, se denomina árbol de unión . El problema dual se puede resolver a partir de un grafo de unión, ya que todas las aristas eliminadas son redundantes. A su vez, el problema se puede resolver de manera eficiente si ese grafo de unión es un árbol, utilizando algoritmos diseñados para problemas de satisfacción de restricciones acíclicas.
Para encontrar un árbol de unión, si lo hay, se puede explotar la siguiente propiedad: si un grafo dual tiene un árbol de unión, entonces los árboles de expansión de peso máximo del grafo son todos árboles de unión, si las aristas están ponderadas por el número de variables que las restricciones correspondientes imponen para que sean iguales. Un algoritmo para encontrar un árbol de unión, si lo hay, procede de la siguiente manera. En el primer paso, se asignan pesos a las aristas: si dos nodos representan restricciones que comparten variables, se asigna un peso a la arista que los une . En el segundo paso, se busca un árbol de expansión de peso máximo. Una vez que se encuentra uno, se verifica si impone la igualdad requerida de variables. Si este es el caso, este árbol de expansión es un árbol de unión.
Otro método para averiguar si un problema de satisfacción de restricciones tiene un árbol de unión utiliza el gráfico primario del problema, en lugar del gráfico dual. El gráfico primario de un problema de satisfacción de restricciones es un gráfico cuyos nodos son variables del problema y cuyos bordes representan la presencia de dos variables en la misma restricción. Existe un árbol de unión para el problema si:
A su vez, la cordalidad se puede comprobar mediante un ordenamiento de las variables según la máxima cardinalidad . Este ordenamiento también se puede utilizar, si se cumplen las dos condiciones anteriores, para encontrar un árbol de unión del problema. Al ordenar las restricciones por su variable más alta según el ordenamiento, un algoritmo para producir un árbol de unión procede de la última a la primera restricción; en cada paso, una restricción se conecta a la restricción que comparte un número máximo de variables con ella entre las restricciones que la preceden en el ordenamiento.
No todos los problemas de satisfacción de restricciones tienen un árbol de unión. Sin embargo, los problemas pueden modificarse para adquirir un árbol de unión. La agrupación de árboles de unión es un método específico para modificar los problemas de manera que adquieran un árbol de unión. Esto se hace mediante la fusión de restricciones, lo que normalmente aumenta el tamaño del problema; sin embargo, resolver el problema resultante es fácil, como lo es para todos los problemas que tienen un árbol de unión.
Los métodos de descomposición generalizan la agrupación de árboles de unión agrupando las variables de tal manera que el problema resultante tenga un árbol de unión. Los métodos de descomposición asocian directamente un árbol con los problemas; los nodos de este árbol son variables asociadas y/o restricciones del problema original. Al fusionar las restricciones basadas en este árbol, se puede producir un problema que tenga un árbol de unión, y este árbol de unión se puede derivar fácilmente del árbol de descomposición. Alternativamente, se puede construir un problema acíclico binario directamente a partir del árbol de descomposición.
