I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this:
Dominating Set on Planar Graphs
- Instance: A planar graph G and an integer k.
- Parameter: k.
- Question: Does there exist a dominating set of size at most k in G?
- Fact: Every planar graph has average degree at most 6.
Reading through some papers I found this simple algorithm [FEL]. It runs in O( (dmax+1)^k * n) where dmax is the maximum degree.
global bool exists=false
function domSet(B, E, k):
if |B|<k
exists=true
else if k>0
choose some u from B
foreach v in (u+N(u)): # N ... neighbour
domSet(B -(v+N(v)), E-I(v), k-1) # I ... incident edges
function main():
given G=(V,E) and k
domSet(V, E, k)
Now to my problem: I have the running time for this algorithm if I know the max. degree, but I'm not succeeding when using the average degree. All in all, the algorithm branches for each neighbour of an inspected vertex. The depth of this tree is at most k. When the degree is upper bounded by dmax, then its easy to calculate the number of vertices of this search tree and therefore the running time. But what about the average degree? How can I find an upper bound for the running time when I just know this average degree?
What I'm trying to express is something like "the search tree might have a high number of branches for some nodes, but there are many others with a low number and we can give an upper bound as f(k)*poly(n)". But I can't find a formal argument for this.
[FEL] http://www.mrfellows.net/papers/C51.pdf (algorithm on page 2)