CompSci 263, Winter 2017, Homework 4

The 3SAT$_{\le k}$ problem takes as input a pair $(F,k)$ where $F$ is a 3-CNF formula and $k$ is an integer parameter, and seeks a truth assignment to the variables of $F$ that satisfies $F$ and has at most $k$ true variables. It is NP-complete (because when $k$ is big it is just 3SAT). We saw in class that, assuming the exponential time hypothesis, it cannot be solved in time $n^{o(k)}$ where $n$ is the number of variables in $F$. Therefore, it is probably not fixed-parameter tractable with its natural parameter. In these problems we consider the problem 2SAT$_{\le k}$, defined in the same way from 2-CNF formulas.

  1. Prove that 2SAT$_{\le k}$ is NP-complete. (Hint: reduce from vertex cover.)

  2. Prove that, for formulas $F$ in which all clauses have at least one negated variable, the instance $(F,k)$ of 2SAT$_{\le k}$ can be solved in polynomial time.

  3. Describe a backtracking algorithm that solves 2SAT$_{\le k}$ in fixed-parameter time. (Hint: Use problem (2) to show that, if the problem cannot be solved directly, it contains a substructure that forces some variables to be positive, and recurse on the different ways to satisfy that substructure.) What is the time for your algorithm?

  4. Describe a kernelization algorithm that solves 2SAT$_{\le k}$ in fixed-parameter time. The kernelization part of your algorithm should run in polynomial time and should transform the problem into an equivalent problem (the kernel) whose size is bounded by a function of $k$. (Hint: try to adapt one of the known kernels for vertex cover.) What is the size of your kernel?

  5. If you apply your kernelization and then run your backtracking algorithm on the resulting kernel, what is the running time of the resulting hybrid algorithm?