Courses
  • IITGN
  • Online
  • Short Courses
  • Other

CS614. Advanced Algorithms. L12 Quiz.

CS614. Advanced Algorithms.

L12 Quiz

Back to the course page

Problem 1. List Coloring

In the List Coloring problem, we are given a graph \(G\) and for each vertex \(v \in V(G)\) there is a set (also called a list) of admissible colors \(L(v) \subseteq N\). The goal is to verify whether it is possible to find a proper vertex coloring c: \(V(G) \rightarrow \mathbb{N}\) of \(G\) such that for ever y vertex \(v\) we have \(c(v) \in L(v)\). In other words, \(L(v)\) is the set of colors allowed for \(v\).

Show a \(2^n n^{\mathcal{O}(1)}\)-time algorithm for List Coloring.

Hint. Read Theorem 10.8 from the Parameterized Algorithms text.

Problem 2. Triangle Packing

In the Triangle Packing problem, we are given an undirected graph \(G\) and a positive integer \(k\), and the objective is to test whether \(G\) has \(k\)-vertex disjoint triangles. Using color coding show that the problem admits an algorithm with running time \(2^{O(k)} n^{O(1)}\).

Made with Quarto and 🩶

 

Content by Neeldhara Misra