CS614. Advanced Algorithms. L07 Quiz.
CS614. Advanced Algorithms.
L07 Quiz
The questions in this problem set are adapted from the textbook on Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.
In the Cluster Vertex Deletion problem, we want to know if a simple undirected graph G has a subset S of at most k vertices such that G \setminus S is a disjoint union of cliques.
Design a 3^k \cdot n^{\mathcal{O}(1)} algorithm for Cluster Vertex Deletion.
Design a 3-approximation algorithm for Cluster Vertex Deletion.
In the MIN-2-SAT problem, we are given a 2 -CNF formula \phi and an integer k, and the objective is to decide whether there exists an assignment for \phi that satisfies at most k clauses.
Show that MIN-2-SAT can be solved in time 2^k n^{\mathcal{O}(1)}.
