# FPT algorithm for 1-BDD

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)$$?

• An earlier version explicitly contained the conjectured running time. Why did you delete it? Apr 8 at 7:34
• Sorry, thought it would have been more general. Apr 10 at 14:52

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.

• Thank you very much!!! Apr 6 at 8:43
• Yuval, In the last improvement, the following statement: $$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)))).$$ Does not hold when $$N(u) \subseteq N(v)$$ because $$T(k−(d−1)+(e_1−1)) = T(k-(d-1))$$. What can be done In this case? May 7 at 5:51
• That’s an excellent question for you. May 7 at 6:44
• The truth is I have been trying to solve it for a long time without success. If you can help me please I would be very happy. By the way, there is no more elegant way to solve It In this running time? May 7 at 12:06
• That's what I could find. You're welcome to search for the original paper proving this bound and to take a peek. May 7 at 13:47