Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is there any FPT algorithm for the above problem running in time $O^*(2^k)$?
Let $v$ be an arbitrary vertex in your graph, of degree $d$. In any solution $D$, either $v \in D$, or at least $d-1$ of its neighbors are in $D$. In this case, we have one branch with parameter $k-1$, and $d$ branches with parameter $k-(d-1)$ (which is progress as long as $d \geq 2$).
If $d = 1$, then we can say more. Let $u$ be the unique neighbor of $v$. If $D$ is any feasible solution, then so is $D \setminus \{v\} \cup \{u\}$. In other words, we can assume without loss of generality that any solution does not contain $v$. Any such solution either contains $u$ or all neighbors of $u$ apart from $v$. If $u$ also has degree $1$ then there is clearly a solution not containing either $u$ or $v$, so we can assume that in this case $u$ has degree at least $2$. In this case, we have one branch with parameter $k-1$, and one branch with parameter $k-(d-1)$.
Denoting by $T(k)$ the worst-case size of the search tree when the parameter in $k$, our ideas so far show that $$ T(k) = T(k-1) + \max_{d \geq 2} (dT(k-(d-1)). $$ Unfortunately, if we choose $d = 2$ then we get $T(k) \geq 3T(k-1)$, whose solution is $T(k) = \Omega(3^k)$.
We can improve on this algorithm by noting that if all vertices have degree $2$ then the problem is easy to solve, since the graph is a union of disjoint cycles, and a cycle of length $\ell$ requires spending $\lceil \ell/2 \rceil$ vertices of $D$. Hence either $v$ has degree at least $3$, or $v$ has degree $1$ (and $u$ has degree at least $2$). This leads to the improved recurrence $$ T(k) = T(k-1) + \max(T(k-1),\max_{d \geq 3} dT(k-(d-1))). $$ Unfortunately, if we choose $d = 3$ then we get $T(k) \geq T(k-1) + 3T(k-2)$, whose solution is $T(k) = \Omega(\bigl(\frac{\sqrt{13}+1}{2}\bigr)^k)$, with a base of roughly $2.3$.
We can improve on this as follows. We can assume that the minimum degree is $2$. Let $v$ be a vertex of degree $d \geq 3$. Any solution either contains $v$, or all of its neighbors, or it contains all but a single neighbor $w$, and all the remaining neighbors of $w$. This leads to one branch with parameter $k-1$, one branch with parameter $k-d$, and $d$ branches with parameters at most $k-d$. Thus $$ T(k) = T(k-1) + \max(\max_{d \geq 1} T(k-d), \max_{d \geq 3}(T(k-d) + \max_{e_1,\ldots,e_d \geq 2} T(k-(d-1)+(e_1-1)) + \cdots + T(k-(d-1)+(e_d-1)))). $$ Using monotonicity, this reduces to $$ T(k) = T(k-1) + \max(T(k-1), \max_{d \geq 3} (d+1)T(k-d)). $$ Using base case of $T(0) = 1$, we can prove by induction that $T(k) = 2^k$. The lower bound is clear. For the upper bound, we need to prove that $(d+1) 2^{k-d} \leq 2^{k-1}$ for all $d \geq 3$, which reduces to $d+1 \leq 2^{d-1}$, an inequality which can be checked directly.
