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.