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.