CS614. Advanced Algorithms. L09 Quiz.
CS614. Advanced Algorithms.
L09 Quiz
A dominating set of a graph \(G\) is a subset of vertices \(S\) such that every vertex in \(G\) either belongs to \(S\) or has a neighbor in \(S\).
Suppose you have an instance of dominating set given by \((G,k)\), which is a YES-instance if and only if \(G\) has a dominating set of size at most \(k\).
Is the following reduction rule safe?
RR. If \(d(v) > k\), then return \((G-v,k-1)\).
( ) Yes (X) No
Briefly justify your answer:
|____|
A connected vertex cover of a graph \(G\) is a subset of vertices \(S\) such that: (a) \(S\) is a vertex cover of \(G\), and (b) \(G[S]\) is a connected subgraph of \(G\).
Suppose you have an instance of connected vertex cover given by \((G,k)\), which is a YES-instance if and only if \(G\) has a connected vertex cover of size at most \(k\).
Design a \(\mathcal{O}(2^k)\) vertex kernel for Connected Vertex Cover.
Hint: What can you say about high degree vertices? How many can \(G\) have?
Follow up hint: What can you say about two vertices that have the same neighbourhood among the high-degree vertices?
Observe that the kernelization argument that we made for Vertex Cover does not work as-is for connected vertex cover. Recall that the reduction rules were the following:
R0. If \(k \leqslant 0\) and \(E\) is non-empty, return a trivial no-instance.
R1. If \(k \geqslant 0\) and \(E\) is empty, return a trivial yes-instance.
R2. If \(v\) is a degree zero vertex, return \((G\setminus \{v\},k)\), i.e, delete \(v\) from \(G\) and keep the budget the same.
R3. If \(v\) is vertex whose degree is more than \(k\), return \((G\setminus \{v\},k-1)\), i.e, delete \(v\) from \(G\) and reduce the budget by one.
Where does it fail? Justify, if possible, with an example.