2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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