Parameterized Complexity for Domination Problems on Degenerate Graphs

Domination problems are one of the classical types of problems in computer science. These problems are considered in many different versions and on different classes of graphs. We explore the boundary between fixed-parameter tractable and W-hard problems on sparse graphs. More precisely, we expand the list of domination probe lems which are fixed-parameter tractable(FPT) for degenerate graphs by proving that CONNECTED k-DOMINATING SET and k-DOMINATING THRESHOLD SET are FPT. From the other side we prove that there are domination problems which are difficult (W[1] or W[2]-hard) for this graph class. The PARTIAL k-DOMINATING SET and (k, r)-CENTER for r >= 2 are examples of such problems. It is also remarked that domination problems become difficult for graphs of hounded average degree.