CS614. Advanced Algorithms. L08 Quiz.

CS614. Advanced Algorithms.

L08 Quiz

Back to the course page

Problem 1. Better Approximation given a k-coloring

Given a k-coloring of a graph G, show that we can find a vertex cover which is a 2\bigl(1−\frac{1}{k}\bigr) approximation.

Hint: use the k-coloring on the vertices of V_{1/2}.

Problem 2. Point Line Cover

In the Point Line Cover problem, we are given a set of n points in the plane and an integer k, and the goal is to check if there exists a set of k lines on the plane that contain all the input points.

Show a kernel for this problem with \mathcal{O}\left(k^2\right) points.