Courses
  • IITGN
  • Online
  • Short Courses
  • Other

CS614. Advanced Algorithms. L09 Quiz.

CS614. Advanced Algorithms.

L09 Quiz

Back to the course page

Problem 1. Dominating Set

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:

|____|

Problem 2. Connected Vertex Cover

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\).

Problem 2.1 Connected Vertex Cover I.

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?

Problem 2.2 Connected Vertex Cover II.

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.

Made with Quarto and 🩶

 

Content by Neeldhara Misra