# FPT algorithm for dominating set

An instance of the Dominating Set problem is given by an undirected graph $$G = (V, E)$$ and an integer $$k$$; it is a ‘yes’-instance if there is a subset of vertices $$S ⊆ V$$ with $$|S| ≤ k$$ such that for each $$v ∈ V$$ we have $$v ∈ S$$ or $$u ∈ S$$ for some $${u, v} ∈ E$$.

I'm trying to show that if the degree of each vertex of $$G$$ is at most 3 then Dominating Set is in FPT with respect to $$k$$.

I thought of maybe creating a bounded search tree algorithm for this, where if all nodes have degree <= 2, it can trivially be solved in $$O(|E|)$$ time. Otherwise consider a node $$v ∈ V$$ with degree 3. Either it's in the dominating set, or one of its neighbours is which results in a $$O(4^k |E|)$$ algorithm. I think there should be something better (maybe using kernels?).

See the FPT algorithm in Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Since the proof applies for $$k$$-degenerate graphs, it also applies for graphs whose maximum degree is $$k$$.