191014K02 | Day 1 Lecture 1

191014K02: Day 2 Tutorial

Back to the Course Page

Definitions

Subgraph Isomorphism

The input is an n-vertex graph G and a k-vertex graph H, and the objective is to test whether there exists a subgraph \widehat{H} of G such that H is isomorphic to \widehat{H}.

Observe that k-Path (discussed in class earlier today) is a special case of Subgraph Isomorphism where H is a path on k vertices. The problem of finding a Clique on k vertices is a special case of Subgraph Isomorphism as well, where H is a clique on k vertices. It is believed that Clique is not FPT, and, consequently, we do not expect that the general Subgraph Isomorphism problem to be FPT when parameterized by k.

Hoeffding’s Inequality

Let X_1, \ldots, X_n be independent random variables such that a_i \leq X_i \leq b_i almost surely. Consider the sum of these random variables, S_n=X_1+\cdots+X_n . Then Hoeffding’s theorem states that, for all t>0, \begin{gathered} \mathrm{P}\left(S_n-\mathrm{E}\left[S_n\right] \geq t\right) \leq \exp \left(-\frac{2 t^2}{\sum_{i=1}^n\left(b_i-a_i\right)^2}\right) \\ \mathrm{P}\left(\left|S_n-\mathrm{E}\left[S_n\right]\right| \geq t\right) \leq 2 \exp \left(-\frac{2 t^2}{\sum_{i=1}^n\left(b_i-a_i\right)^2}\right) \end{gathered}

Here \mathrm{E}\left[S_{\mathrm{n}}\right] is the expected value of S_n.

Problems

1. Show that the number of inclusion minimal vertex covers of size at most k is at most 2^k. (Use the algorithm from class.)

2. Generalize the Vertex Cover algorithm that we saw today to Set Cover in which every element appears in at most d sets.

3. Feedback Vertex Set as Hitting Set. Why don’t we get a O(\log n) approximation for FVS via the O(\log n) approximation for Set Cover¹?

4. Use Markov inequality to show that: \operatorname{Pr}[{\color{indianred}|S| \leqslant 2 \cdot |\text{OPT}|}] \geqslant \Omega(1 /|\text{OPT}|)

5. Come up with an algorithm to solve an instance of subgraph isomorphism (G, H) in time 2^{d k} k ! n^{\mathcal{O}(1)} and in time 2^{d k} k^{\mathcal{O}(d \log d)} n^{\mathcal{O}(1)}. Here, |V(G)|=n,|V(H)|=k, and the maximum degree of G is bounded by d.

6. Generalize the color coding approach for Longest Path to: (a) k-Cycle where H is a cycle on k vertices, (b) Tree Subgraph Isomorphism, where H is restricted to being a tree on k vertices.

7. Design a randomized algorithm running in time 2^{O\left(\sqrt{k} \log ^2 k\right)}+n^{O(1)} for the problem of finding a feedback arc set of size at most k in a tournament on n vertices.

Footnotes

1. Note that Set Cover and Hitting Set are equivalent problems.