Many tasks in automated reasoning can be modeled as weighted constraint satisfaction problems over Boolean variables (Boolean WCSPs). Tractable classes of such problems have traditionally been identified by exploiting either: (a) the topology of the associated constraint network, or (b) the structure of the weighted constraints. In this paper, we introduce the notion of a constraint composite graph (CCG) associated with a given (Boolean) WCSP. The CCG provides a unifying framework for characterizing/exploiting both the graphical structure of the constraint network as well as the structure of the weighted constraints. We show that a given (Boolean) WCSP can be reduced to the problem of computing the minimum weighted vertex cover for its associated CCG; and we establish the following two important results: (1) “the CCG of a given Boolean WCSP has the same treewidth as its associated constraint network,” and (2) “many classes of Boolean WCSPs that are tractable by virtue of the structure of their weighted constraints have associated CCGs that are bipartite in nature.”