2
$\begingroup$

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)

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Hint: You have a bound on the average degree; can you prove the existence of a vertex with low degree? $\endgroup$ – j_random_hacker Nov 12 '16 at 13:42
  • $\begingroup$ I can show this for a uniform distribution, i.e. if each vertex - branching - node can be found equally often in the search tree. But I don't know how the distribution of the branching nodes looks like. $\endgroup$ – Harry Nov 12 '16 at 14:56
  • $\begingroup$ "Choose some u from B" -- you can pick any vertex here, so you might as well pick the one with lowest degree. Also I didn't understand your remark about "uniform distribution" -- existence of a low-degree vertex can be proven without any additional assumptions beyond the upper bound on average degree. $\endgroup$ – j_random_hacker Nov 12 '16 at 20:16
  • $\begingroup$ each planar graph has a vertex with degree at most 5. The algorithm lets us choose from the (remaining) planar graph an arbitrary vertex, so let's always choose the low degree vertex. This vertex is definitely removed (among others) in the next step, we again get a planar graph. This one again has a low degree vertex, so let's choose this one. This would yield an algorithm of O(5^k * n) but NESETRIL [1] says that the algorithm has O(11^k * n) running time, so there must be a flaw in my argumentation. [1] NESETRIL - STRUCTURAL PROPERTIES OF SPARSE GRAPHS $\endgroup$ – Harry Nov 12 '16 at 21:52
  • $\begingroup$ just to let you know: there was an error in the task - there is no easy solution to find an upper bound regarding the average degree. The reason is that we can find a minimum degree vertex each time, but we can not guarantee that this one is undominated. Of course, we can still use the white-black decomposition shown in several papers. $\endgroup$ – Harry Nov 27 '16 at 16:39

Your Answer

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

Browse other questions tagged or ask your own question.