Lifting Techniques for Weighted Constraint Satisfaction Problems.
T. K. Satish Kumar · 2008
In this paper, we identify rich tractable classes of Weighted Constraint Satisfaction Problems (WCSPs). Our results stem from employing a set of transformation techniques—referred to as “Lifting”—that considers each constraint locally. We show that, in general, WCSPs are reducible to minimum weighted vertex cover problems in tripartite graphs; and many tractable classes of WCSPs can be recognized by their reducibility to minimum weighted vertex cover problems in bipartite graphs. We examine the implications of our approach when combined with other mathematical tools, and provide a framework for tightly characterizing the complexity of solving a given instance of the WCSP. 1