Abstract
In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set \(S \subseteq V(G) \cup E(G)\) of cardinality at most k such that every element \(x \in (V(G) \cup E(G)) \setminus S\) is either adjacent to or incident with an element of S. We show that mds can be solved in time \({7.465^k n^{\mathcal {O}(1)}} \) on general graphs, and in time \(2^{\mathcal {O}(\sqrt{k})} n^{\mathcal {O}(1)}\) on planar graphs. We complement this result by showing that mds does not admit an algorithm with running time \(2^{o(k)} n^{\mathcal {O}(1)}\) unless the Exponential Time Hypothesis (ETH) fails, and that it does not admit a polynomial kernel unless coNP \( \subseteq \mathsf{NP / poly}\). In addition, we provide an algorithm which, given a graph G together with a tree decomposition of width \(\mathsf{tw}\), solves mds in time \(6^{\mathsf{tw}} n^{\mathcal {O}(1)}\). We finally show that unless the Set Cover Conjecture (SeCoCo) fails, mds does not admit an algorithm with running time \(\mathcal {O}((2-\epsilon )^{\mathsf{tw}(G)} n^{\mathcal {O}(1)})\) for any \(\epsilon >0\), where \(\mathsf{tw}(G)\) is the tree-width of G.
The research leading to these results have received funding from the European Research Council via ERC Advanced Investigator Grant 267959.
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
Notes
- 1.
\(\mathcal {O}^\star \) notation suppresses the polynomial factor. That is, \(\mathcal {O}(f(k)n^{\mathcal {O}(1)})=\mathcal {O}^\star (f(k))\).
References
Alavi, Y., Behzad, M., Lesniak-Foster, L.M., Nordhaus, E.A.: Total matchings and total coverings of graphs. J. Graph Theor. 1(2), 135–140 (1977)
Alavi, Y., Liu, J., Wang, J., Zhang, Z.: On total covers of graphs. Discrete Math. 100(1–3), 229–233 (1992)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets möbius: fast subset convolution. In: STOC, pp. 67–74 (2007)
Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c\({}^{\text{k}}\) n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317–378 (2016). http://dx.doi.org/10.1137/130947374
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21275-3
Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlström, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41:1–41:24 (2016)
Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDS. ACM Trans. Algorithms 11(2), 13:1–13:20 (2014)
Erdös, P., Meir, A.: On total matching numbers and total covering numbers of complementary graphs. Discrete Math. 19(3), 229–233 (1977)
Fernau, H.: On parameterized enumeration. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 564–573. Springer, Heidelberg (2002). doi:10.1007/3-540-45655-4_60
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Gu, Q., Tamaki, H.: Improved bounds on the planar branchwidth with respect to the largest grid minor size. Algorithmica 64(3), 416–453 (2012)
Hatami, P.: An approximation algorithm for the total covering problem. Discuss. Math. Graph Theor. 27(3), 553–558 (2007)
Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. CRC Press, Boca Raton (1998)
Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R., McRae, A., Majumdar, A.: Domination, independence and irredundance in total graphs: a brief survey. In: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs. vol. 2, pp. 671–683 (1995)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Lan, J.K., Chang, G.J.: On the mixed domination problem in graphs. Theor. Comput. Sci. 476, 84–93 (2013)
Majumdar, A.: Neighborhood hypergraphs: a framework for covering and packing parameters in graphs. Ph.D. thesis, Clemson University (1992)
Manlove, D.: On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Appl. Math. 91(1–3), 155–175 (1999)
Meir, A.: On total covering and matching of graphs. J. Comb. Theor. Ser. B 24(2), 164–168 (1978)
Micali, S., Vazirani, V.V.: An \(\cal{O}(\sqrt{|V|} |E|)\) algorithm for finding maximum matching in general graphs. In: FOCS, pp. 17–27 (1980)
Peled, U.N., Sun, F.: Total matchings and total coverings of threshold graphs. Discrete Appl. Math. 49(1–3), 325–330 (1994)
Rajaati, M., Hooshmandasl, M.R., Dinneen, M.J., Shakiba, A.: On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width. CoRR abs/1612.08234 (2016)
Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theor. Ser. B 62(2), 323–348 (1994)
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364–372 (1980)
Zhao, Y., Kang, L., Sohn, M.Y.: The algorithmic complexity of mixed domination in graphs. Theor. Comput. Sci. 412(22), 2387–2392 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jain, P., Jayakrishnan, M., Panolan, F., Sahu, A. (2017). Mixed Dominating Set: A Parameterized Perspective. In: Bodlaender, H., Woeginger, G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2017. Lecture Notes in Computer Science(), vol 10520. Springer, Cham. https://doi.org/10.1007/978-3-319-68705-6_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-68705-6_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68704-9
Online ISBN: 978-3-319-68705-6
eBook Packages: Computer ScienceComputer Science (R0)