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)}\).