Abstract
The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P⊆V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aazami, A., Stilp, M.D.: Approximation algorithms and hardness for domination with propagation. In: Proc. 10th APPROX/11th RANDOM. Lecture Notes in Computer Science, vol. 4627, pp. 1–15. Springer, Berlin (2007)
Adjih, C., Jacquet, P., Viennot, L.: Computing connected dominating sets with multipoint relays. Ad Hoc Sens. Wirel. Netw. 1(1–2), 27–39 (2005)
Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica 33(4), 461–493 (2002)
Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined search tree technique for Dominating Set on planar graphs. J. Comput. Syst. Sci. 71(4), 385–405 (2005)
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for Dominating Set. J. ACM 51(3), 363–384 (2004)
Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Proc. 5th LATIN. Lecture Notes in Computer Science, vol. 2286, pp. 613–628. Springer, Berlin (2002)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation—Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)
Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Proc. 32nd WG. Lecture Notes in Computer Science, vol. 4271, pp. 1–14. Springer, Berlin (2006)
Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Comput. 11, 191–199 (1982)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)
Brueni, D.J., Heath, L.S.: The PMU placement problem. SIAM J. Discrete Math. 19(3), 744–761 (2005)
Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proc. 16th SODA, pp. 590–601. ACM/SIAM, New York (2005)
Dewdney, A.K.: Fast Turing reductions between problems in NP: chap. 4; reductions between NP-complete problems. Technical report, Department of Computer Science, University of Western Ontario, Canada, 1981
Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Appl. Math. 154(6), 1023–1027 (2006)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
Feige, U.: A threshold of ln n for approximating Set Cover. J. ACM 45(4), 634–652 (1998)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Guo, J., Hüffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Proc. 1st IWPEC. Lecture Notes in Computer Science, vol. 3162, pp. 162–173. Springer, Berlin (2004)
Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs: applied to electric power networks. SIAM J. Discrete Math. 15(4), 519–529 (2002)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Pure and Applied Mathematics, vol. 209. Dekker, New York (1998)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs, Pure and Applied Mathematics, vol. 208. Dekker, New York (1998)
Haynes, T.W., Henning, M.A.: Domination in graphs. In: Gross, J.L., Yellen, J. (eds.) Handbook of Graph Theory, pp. 889–909. CRC Press, Boca Raton (2004)
Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Appl. Math. 36, 25–34 (1992)
Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)
Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Parameterized power domination complexity. Inf. Process. Lett. 98(4), 145–149 (2006)
Kratsch, D.: Algorithms. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.) Domination in Graphs: Advanced Topics, pp. 191–231. Dekker, New York (1998)
Liao, C.S., Lee, D.T.: Power dominating problem in graphs. In: Proc. 11th COCOON. Lecture Notes in Computer Science, vol. 3595, pp. 818–828. Springer, Berlin (2005)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)
Raible, D.: Algorithms and complexity results for power domination in networks. Master’s thesis, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Germany (2005). (In German)
Reed, B.A.: Algorithmic aspects of tree width. In: Reed, B.A., Sales, C.L. (eds.) Recent Advances in Algorithms and Combinatorics, pp. 85–107. Springer, Berlin (2003)
Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Proc. 3rd WADS. Lecture Notes in Computer Science, vol. 709, pp. 610–621. Springer, Berlin (1993)
Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10(4), 529–550 (1997)
Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appears in the proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT’05), vol. 3623 in LNCS, pp. 172–184, Springer (2005). Work supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group PIAF (fixed-parameter algorithms), NI 369/4. Significant portions of this work were done while all authors were affiliated with the Universität Tübingen.
Rights and permissions
About this article
Cite this article
Guo, J., Niedermeier, R. & Raible, D. Improved Algorithms and Complexity Results for Power Domination in Graphs. Algorithmica 52, 177–202 (2008). https://doi.org/10.1007/s00453-007-9147-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9147-x