4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ An earlier version explicitly contained the conjectured running time. Why did you delete it? $\endgroup$ – Yuval Filmus Apr 8 at 7:34
  • $\begingroup$ Sorry, thought it would have been more general. $\endgroup$ – Jumanji Halastra Apr 10 at 14:52
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you very much!!! $\endgroup$ – Jumanji Halastra Apr 6 at 8:43
  • $\begingroup$ 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? $\endgroup$ – John19 May 7 at 5:51
  • $\begingroup$ That’s an excellent question for you. $\endgroup$ – Yuval Filmus May 7 at 6:44
  • $\begingroup$ 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? $\endgroup$ – John19 May 7 at 12:06
  • $\begingroup$ That's what I could find. You're welcome to search for the original paper proving this bound and to take a peek. $\endgroup$ – Yuval Filmus May 7 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.