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.
