Abstract
The Paired Domination problem is one of the well-studied variants of the classical Dominating Set problem. In a graph G on n vertices, a dominating set D (set of vertices such that \(N[D]=V(G)\)) is called a paired dominating set of G, if G[D] has perfect matching. In the Paired Domination problem, given a graph G and a positive integer k, the task is to check whether G has a paired dominating set of size at most k. The problem is a variant of the Dominating Set problem, and hence inherits most of the hardness of the Dominating Set problem; however, the same cannot be said about the algorithmic results. In this paper, we study the problem from the perspective of parameterized complexity, both from solution and structural parameterization, and obtain the following results.
-
1.
We design an (non-trivial) exact exponential algorithm running in time \(\mathcal {O}(1.7159^n)\).
-
2.
It admits Strong Exponential Time Hypothesis (SETH) optimal algorithm parameterized by the treewidth (\(\textsf {tw}\)) of the graph G. The algorithm runs in time \(4^{\textsf {tw}} n^{\mathcal {O}(1)}\); and unless SETH fails, there is no algorithm running in time \((4 - \epsilon )^{\textsf {tw}} n^{O(1)}\) for any \(\epsilon > 0\).
-
3.
We design an \(4^d n^{O(1)}\) algorithm parameterized by the distance to cluster graphs. We complement this result by proving that the problem does not admit a polynomial kernel under this parameterization and under parameterization by vertex cover number.
-
4.
Paired Domination admits a polynomial kernel on graphs that exclude a biclique \(K_{i,j}\).
-
5.
We also prove that one of the counting versions of Paired Domination parameterized by cliquewidth admits \(n^{2\textsf {cw}}n^{O(1)}\) time algorithm parameterized by cliquewidth (cw). However, it does not admit an FPT algorithm unless #SETH is false.
N. Andreev—Independent Researcher, Dubai, UAE.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363–384 (2004)
Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544–556 (2009)
Bodlaender, H.L., van Leeuwen, E.J., van Rooij, J.M.M., Vatshelle, M.: Faster algorithms on branch and clique decompositions. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 174–185. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_17
Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 269–280. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31856-9_22
Chen, L., Lu, C., Zeng, Z.: Labelling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim. 19(4), 457–470 (2010)
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes of graphs. In: Foundations of Software Technology and Theoretical Computer Science—FSTTCS 2009, LIPIcs. Leibniz International Proceedings in Informatics, vol. 4, pp. 157–168. Schloss Dagstuhl – Leibniz Center for Informatics, Wadern (2009)
Desormeaux, W.J., Henning, M.A.: Paired domination in graphs: a survey and recent results. Util. Math. 94, 101–166 (2014)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Cham (2012)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873–921 (1995)
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9:1–9:17 (2008)
Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: linear kernel and exponential speed-up. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 581–592. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_50
Hanaka, T., Ono, H., Otachi, Y., Uda, S.: Grouped domination parameterized by vertex cover, twin cover, and beyond. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, vol. 13898, pp. 263–277. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30448-4_19
Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (eds.): Topics in Domination in Graphs. Developments in Mathematics, vol. 64. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51117-3
Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (eds.): Structures of Domination in Graphs. Developments in Mathematics, vol. 66. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-58892-2
Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.): Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, vol. 209
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker Inc., New York (1998)
Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Netw. Int. J. 32(3), 199–206 (1998)
Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), Article no. 13, 30 (2018)
Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 11:1–11:23 (2012)
Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203–225 (2008)
van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 566–577. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04128-0_51
Tripathi, V., Kloks, T., Pandey, A., Paul, K., Wang, H.L.: Complexity of paired domination in AT-free and planar graphs. Theor. Comput. Sci. 930, 53–62 (2022)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Andreev, N., Bliznets, I., Kundu, M., Saurabh, S., Tripathi, V., Verma, S. (2024). Parameterized Complexity of Paired Domination. In: Rescigno, A.A., Vaccaro, U. (eds) Combinatorial Algorithms. IWOCA 2024. Lecture Notes in Computer Science, vol 14764. Springer, Cham. https://doi.org/10.1007/978-3-031-63021-7_40
Download citation
DOI: https://doi.org/10.1007/978-3-031-63021-7_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-63020-0
Online ISBN: 978-3-031-63021-7
eBook Packages: Computer ScienceComputer Science (R0)