CS614. Advanced Algorithms. L12 Quiz.
CS614. Advanced Algorithms.
L12 Quiz
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.
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)}\).