Constraint Composite Graph

The constraint composite graph is a node-weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K. Satish Kumar), the idea of the constraint composite graph is a big step towards unifying different approaches for exploiting "structure" in weighted constraint satisfaction problems. A weighted constraint satisfaction problem (WCSP) is a generalization of a constraint satisfaction problem in which the constraints are no longer "hard," but are extended to specify non-negative costs associated with the tuples. The goal is then to find an assignment of values to all the variables from their respective domains so that the total cost is minimized. Weighted constraint satisfaction problems find innumerable applications in artificial intelligence and computer science. They are also variously referred to as markov random fields (in statistics and signal processing) and energy minimization problems (in physics).

While weighted constraint satisfaction problems are NP-hard to solve in general, several subclasses can be solved in polynomial time when their weighted constraints exhibit specific kinds of numerical structure. Tractable subclasses can also be identified by analyzing the way constraints are placed over the variables. Specifically, a weighted constraint satisfaction problem can be solved in time exponential only in the treewidth of its variable-interaction graph (constraint network). However, a major drawback of the constraint network is that it does not provide a computational framework for leveraging the numerical structure of the weighted constraints.

Unlike the constraint network, the constraint composite graph provides a unifying framework for representing both the graphical structure of the variable-interactions as well as the numerical structure of the weighted constraints. It can be constructed using a simple polynomial-time procedure; and a given weighted constraint satisfaction problem is reducible to the problem of computing the minimum weighted vertex cover for its associated constraint composite graph. The "hybrid" computational properties of the constraint composite graph are reflected in the following two important results:

(Result 1) The constraint composite graph of a given weighted constraint satisfaction problem has the same treewidth as its associated constraint network.

(Result 2) Many subclasses of weighted constraint satisfaction problems that are tractable by virtue of the numerical structure of their weighted constraints have associated constraint composite graphs that are bipartite in nature.

Result 1 shows that the constraint composite graph can be used to capture the graphical structure of the variable-interactions (since a minimum weighted vertex cover for any graph can be computed in time exponential only in the treewidth of that graph). Result 2 shows that the constraint composite graph can also be used to capture the numerical structure of the weighted constraints (since a minimum weighted vertex cover can be computed in polynomial time for bipartite graphs).

Empirically, when solving a WCSP, it has been shown that it is more advantageous to apply message passing algorithms and integer linear programming on the WCSP's constraint composite graph than on the WCSP directly.