Courses
  • IITGN
  • Online
  • Short Courses
  • Other

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.

Made with Quarto and 🩶

 

Content by Neeldhara Misra