-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFPA-Exercises-03.tex
64 lines (49 loc) · 4.85 KB
/
FPA-Exercises-03.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
% LTeX: language=en_US
\documentclass[english]{uebung_cs}
\usepackage{settings}
\blattnummer{3}
\blattname{Problem set \theblattnummer: Iterative Compression and Randomization}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\textbf{Overview:} With this problem set, you can train developping FPT algorithms using iterative compression and randomization.
\textbf{Instructions:} For each skill, select \textbf{exactly one} problem below and submit your solution in \href{https://moodle.studiumdigitale.uni-frankfurt.de/moodle/course/view.php?id=6259}{Moodle}; in your submission, make sure to repeat the problem that you are solving.
The problems are roughly ordered by difficulty, choose a problem that you find non-trivial and interesting. (You are of course welcome to try the other problems as well and ask us for feedback.)
\textbf{Note:} On this problem set, we write \emph{one-sided bounded-error randomized algorithm} for any randomized algorithm that has a one-sided error probablitity of at most~$1/2$.
\begin{skill}[Iterative Compression][\mandatory]
I can design FPT algorithms using iterative compression. \normalfont (For an example, see Section~4.1 and~4.2 in \cygan{})
\end{skill}
\begin{exercise}[3-Hitting Set]
Obtain an algorithm for 3-\emph{Hitting Set} running in time $2.4656^kn^{O(1)}$ using iterative compression. Generalize this algorithm to obtain an algorithm for d-\emph{Hitting Set} running in time \[((d-1)+0.4656)^kn^{O(1)} \,. \]
\end{exercise}
\begin{exercise}[Independent feedback vertex set][\hard]
A set $X \subseteq V(G)$ of an undirected graph $G$ is called an \emph{independent feedback vertex set} if $G[X]$ is independent and $G - X$ is acyclic. In the \emph{Independent Feedback Vertex Set} problem, we are given as input a graph $G$ and a positive integer $k$, and the objective is to decide whether $G$ has an independent feedback vertex set of size at most $k$. Show that this problem is fixed-parameter tractable by obtaining an algorithm running in time $5^kn^{O(1)}$ using iterative compression.
\end{exercise}
\begin{skill}[Color coding][\mandatory]
I can design randomized FPT algorithms by applying the color coding technique. \normalfont (For more context, see Chapter~5 in \cygan{})
\end{skill}
\begin{exercise}[Triangle Packing]
%[\easy]
In the \emph{Triangle Packing} problem, we are given an undirected graph $G$ and a positive integer $k$, and the objective is to test whether $G$ has $k$ vertex-disjoint triangles. Use color coding to design a one-sided bounded-error randomized algorithm for this problem with running time $2^{O(k)} n^{O(1)}$.
\end{exercise}
\begin{exercise}[Tree Subgraph Isomorphism]
In the \emph{Tree Subgraph Isomorphism} problem, we are given an undirected graph $G$ and a tree~$T$ on~$k$ vertices, and the objective is to decide whether there exists a subgraph in~$G$ that is isomorphic to~$T$. Use color coding to design a one-sided bounded-error randomized algorithm for this problem with running time $2^{O(k)}n^{O(1)}$.
\end{exercise}
\sepline
\paragraph*{Additional problems.} The following problems help you gain a deeper understanding of the course material. Problem \ref{vertexcover} combines your knowledge of bounded search trees from last week with the technique of probability amplification.
\begin{exercise}[Vertex-Cover Probability Amplification][easy]\label{vertexcover}
Design a randomized polynomial-time algorithm $\mathbb{A}$ that, given a graph $G$ and a positive integer $k$, outputs $0$ with probability $1$ if $G$ has no vertex cover of size $k$ and outputs $1$ with probability $\geq 2^{-k}$ if $G$ has a vertex cover of size $k$.
Then use $\mathbb{A}$ to obtain a randomized algorithm for Vertex Cover running in time $2^{O(k)} n^{O(1)}$ that succeeds in the positive case with probability $\geq 1/2$. Please formally prove the bound on the success probability.
\end{exercise}
\begin{exercise}[Challenging graph problem][\hard]
Consider the following problem: Given an undirected graph $G$ and positive integers $k$ and $q$, find a set $X$ of at most $k$ vertices such that $G - X$ has at least two components of size at least~$q$.
\begin{enumerate}
\item%\cygan{}, 5.3
Show that this problem can be solved in time $2^{O(q+k)}n^{O(1)}$ by a one-sided bounded-error randomized algorithm.
\item Assuming $q>k$, show that the problem can be solved in time $q^{O(k)}n^{O(1)}$ by a one-sided bounded-error randomized algorithm.
\end{enumerate}
\end{exercise}
% \cygan{}, Exercise 5.12
% \begin{exercise}[todo: skill]
% In the \emph{Partial Dominating Set} problem, we are given an undirected graph $G$ and positive integers $k$ and $t$, and the goal is to check whether there exists a set $X\subseteq V(G)$ of size at most $k$ such that $|N_G[X]| \geq t$. Obtain an algorithm running in time $2^{O(t)}n^{O(1)}$ for the problem.
% \end{exercise}
\end{document}