In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true.Show that Min-Ones-2-SAT admits a polynomial kernel.

What I did

  1. check if I can satisfy a 2-CNF Sat with k variables set to true.
  2. Read about 2-CNF Sat and deduced that I need to get the directed implication graph.
  3. Transform the implication graph to a undirected graph (by reducing the 2-CNF Sat boolean formula)
  4. The problem now looks like a vertex cover problem

My Question How do I get from the implication graph to the undirected graph? I did some research and found out that I needed to get φ* and then derive the undirected graph from φ*+ which includes only the positive literals from φ* but I am not quite sure I understand what is happening there (resource: https://www.sciencedirect.com/science/article/pii/S0304397513005355#br0030)

  • $\begingroup$ en.wikipedia.org/wiki/… says that Min-Ones-2-SAT (which it calls Weighted 2-satisfiability) is W[1]-complete, meaning it is not in FPT unless all W[1]-complete problems are. And if it is not in FPT then it certainly has no polynomial kernel. $\endgroup$ – j_random_hacker Sep 23 '19 at 19:56
  • $\begingroup$ I read this link before but I did not understand what W[1] Complete means $\endgroup$ – Sara Kat Sep 23 '19 at 20:12
  • $\begingroup$ Think of it as the equivalent of NP Hard in the FPT world: A set of problems which are all "as hard as each other", and seem resistant to FPT techniques though no one has yet been able to prove that they are not (or are) in FPT. $\endgroup$ – j_random_hacker Sep 23 '19 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.