Fixed-Parameter Tractability Of A Class Of Constraint Satisfaction Problems

Let be an instance of binary boolean CSP. Consider the following problem:whether it is possible to remove at most constraints of such that the remainingconstraints are satis?able. We call it Almost CSP problem. It is easy to see that thisproblem is NP-hard. In this thesis, we study the problem from the point of view ofparameterized complexity, where is the parameter.Many natural combinatorial problems can be expressed in terms of Almost CSP,consider the following two examples:(1) When all the relations are inequality=?, Almost CSP is equivalent to decidingwhether one can remove at most edges in an undirected graph such that theremaining graph is a bipartite graph.(2) When all the relations are of OR type, then Almost CSP is equivalent to givena 2-SAT formula, deciding whether one can remove at most clauses such thatthe remaining formula is satis?able.These two special cases have been shown to be ?xed parameter tractable, and it is natu-ral to conjecture that the general Almost CSP problem is also ?xed parameter tractable.This thesis provides some evidence for the conjecture. We de?ne a class of de-cisive relations and prove that when restricting all the types of relations in the inputinstance to this class, Almost CSP is ?xed parameter tractable. Since=? is one of thedecisive relations, this result generalizes (1). Furthermore, we show that while thereis no OR type relations in the input instance, the problem remains ?xed parametertractable.