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
- check if I can satisfy a 2-CNF Sat with k variables set to true.
- Read about 2-CNF Sat and deduced that I need to get the directed implication graph.
- Transform the implication graph to a undirected graph (by reducing the 2-CNF Sat boolean formula)
- 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)