Notes - ADS HT24, Parameterised complexity
Flashcards
What is a parameterisation of a decision problem $\mathcal P$?
A computable function $p$ that maps each input instance $I$ to an integer value $k$.
What does it mean for a decision problem $\mathcal P$ to be fixed-parameter tractable (FPT) with respect to a parameter $p$?
There exists $c > 0$, a computable function $g$ and an algorithm $\mathcal A$ such that given an instance $I$ of $\mathcal P$ with parameter value $p = k$, $\mathcal A$ decides whether $I$ is a YES-instance of $\mathcal P$ in time $g(k) \cdot \vert I \vert ^c$.
The $\textbf{VertexCover}$ decision problem is:
- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.
Can you describe an $O(2^k \vert E \vert )$ bounded search tree algorithm for this problem, and show that it has the required running time?
- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.
- If $G$ has no edges and $k \ge 0$, output YES.
- If $G$ has still has edges and $k = 0$, output NO.
- Otherwise consider an arbitrary edge $\{u, v\}$.
- Either $u$ or $v$ must belong to the vertex cover
- Try both possibilities:
- Add $u$ to the vertex cover, and recurse on $(G\setminus \{u\}, k-1)$
- Add $v$ to the vertex cover, and recurse on $(G\setminus \{v\}, k-1)$
We have a binary search tree with depth $k$, hence the time complexity is $O(2^k \vert G \vert ^c)$ for some $c$.
The $\textbf{VertexCover}$ decision problem is:
- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.
There is a $O(2^k \vert E \vert )$ bounded search tree algorithm for this problem given by
- Consider an arbitrary edge $\{u, v\}$.
- Either $u$ or $v$ must belong to the vertex cover
- Try both possibilities:
- Add $u$ to the vertex cover, and recurse on $(G\setminus \{u\}, k-1)$
- Add $v$ to the vertex cover, and recurse on $(G\setminus \{v\}, k-1)$
- (Base case $k = 0$, output YES if $G$ has no edges)
We have a binary search tree with depth $k$, hence the time complexity is $O(2^k \vert G \vert ^c)$ for some $c$.
Can you describe a modification of this algorithm that has better dependence on $k$?
- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.
- Add $u$ to the vertex cover, and recurse on $(G\setminus \{u\}, k-1)$
- Add $v$ to the vertex cover, and recurse on $(G\setminus \{v\}, k-1)$
- If every vertex in $G$ has degree $\le 2$, compute answer in time $O( \vert E \vert )$.
- Otherwise, let $v$ be a vertex of degree $\ge 3$
- Either $v$ belongs to the vertex cover or all three of its neighbours $u _ 1, u _ 2, u _ 3$ belong to the the vertex cover. Try each of the two cases:
- Add $v$ to the vertex cover, and recurse on $(G\setminus\{v\}, k-1)$
- Add $u _ 1, u _ 2, u _ 3$ to the vertex cover, and recurse on $(G \setminus \{u _ 1, u _ 2, u _ 3}, k - 3)$
Clearly the search tree is going to be smaller (in fact, this algorithm has time complexity $O(1.466^k \vert G \vert ^c)$.
The $\mathbf{MaxIndependentSet}$ optimisation problem is:
- Input: Graph $G = (V, E)$
- Output: The largest independent set, where a independent set is a set $S \subseteq V$ of mutually non-adjacent vertices?
Can you describe a $O(1.381^k \vert E \vert )$ bounded search tree algorithm for this problem, given that
\[t(k) \le t(k-1) + t(k-4) \implies t(k) \le 1.381^k\]
- Input: Graph $G = (V, E)$
- Output: The largest independent set, where a independent set is a set $S \subseteq V$ of mutually non-adjacent vertices?
- If every vertex in $G$ has degree $\le 2$, compute answer in time $O( \vert E \vert )$.
- Otherwise, let $v$ be a vertex of degree $\ge 3$
- Either $v$ belongs to the max independent set (in which case none of its neighbours do), or it doesn’t. Try each of the two cases:
- Add $v$ to independent set, and let $S _ 1$ be the size of the max independent set in $G \setminus (\{v \cup N(v)\})$
- Don’t add $v$ to independent set, and let $S _ 2$ be the size of the max independent set in $G\setminus \{v\}$.
- Output $\max\{S _ 1 + 1, S _ 2\}$.
We have that if $t(k)$ is the number of leaves in the search tree for $k$ vertices,
\[t(k) \le t(k - 1) + t(k-4)\]By the handy hint, this implies the algorithm is
\[O(1.381^n|E|)\]Suppose we are looking at the parameterised complexity of some algorithm. What does the notation
\[O^\ast(g(k))\]
mean?
The algorithm has time complexity
\[O(g(k) \cdot |x|^c)\]for some $c$ and parameter $k$. (This is useful for ignoring a polynomial time base case, since typically $g$ will be exponential).