{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T07:05:43Z","timestamp":1784012743894,"version":"3.55.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T00:00:00Z","timestamp":1783987200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T00:00:00Z","timestamp":1783987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,9]]},"DOI":"10.1007\/s00224-026-10288-5","type":"journal-article","created":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:24:48Z","timestamp":1784010288000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Generalizations of Edge Dominating Set"],"prefix":"10.1007","volume":"70","author":[{"given":"Shubhada","family":"Aute","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Souvik","family":"Saha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anannya","family":"Upasana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,14]]},"reference":[{"issue":"2","key":"10288_CR1","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009). https:\/\/doi.org\/10.1137\/070683933","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10288_CR2","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating Set Cover. J. ACM 45(4), 634\u2013652 (1998). https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J. ACM"},{"key":"10288_CR3","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 624\u2013633. ACM, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"key":"10288_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco (1979)"},{"key":"10288_CR5","doi-asserted-by":"publisher","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Aho, A.V., Borodin, A., Constable, R.L., Floyd, R.W., Harrison, M.A., Karp, R.M., Strong, H.R. (eds.) Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, pp. 38\u201349. ACM, New York, NY, USA (1973). https:\/\/doi.org\/10.1145\/800125.804034","DOI":"10.1145\/800125.804034"},{"key":"10288_CR6","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, Held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10288_CR7","unstructured":"Lin, B., Ren, X., Sun, Y., Wang, X.: Constant approximating parameterized k-SetCover is W[2]-hard (2022). arXiv:2202.04377"},{"key":"10288_CR8","doi-asserted-by":"publisher","unstructured":"Aute, S., Panolan, F., Saha, S., Saurabh, S., Upasana, A.: Parameterized complexity of generalizations of Edge Dominating Set. In: Kr\u00e1lovic, R., Kurkov\u00e1, V. (eds.) SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20-23, 2025, Proceedings, Part I. Lecture Notes in Computer Science, vol. 15538, pp. 65\u201379. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-82670-2_6","DOI":"10.1007\/978-3-031-82670-2_6"},{"issue":"3","key":"10288_CR9","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge Dominating Sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980). https:\/\/doi.org\/10.1137\/0138030","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"10288_CR10","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight Edge Dominating Set problem. Discret. Appl. Math. 118(3), 199\u2013207 (2002). https:\/\/doi.org\/10.1016\/S0166-218X(00)00383-8","journal-title":"Discret. Appl. Math."},{"key":"10288_CR11","doi-asserted-by":"publisher","unstructured":"Fernau, H.: Edge Dominating Set: Efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13-15, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4169, pp. 142\u2013153. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_13","DOI":"10.1007\/11847250_13"},{"key":"10288_CR12","doi-asserted-by":"publisher","unstructured":"Iwaide, K., Nagamochi, H.: An improved algorithm for parameterized Edge Dominating Set problem. In: Rahman, M.S., Tomita, E. (eds.) WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings. Lecture Notes in Computer Science, vol. 8973, pp. 234\u2013245. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-15612-5_21","DOI":"10.1007\/978-3-319-15612-5_21"},{"key":"10288_CR13","doi-asserted-by":"publisher","unstructured":"Xiao, M., Kloks, T., Poon, S.: New parameterized algorithms for the Edge Dominating Set problem. In: Murlak, F., Sankowski, P. (eds.) Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6907, pp. 604\u2013615. Springer, Berlin, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22993-0_54","DOI":"10.1007\/978-3-642-22993-0_54"},{"key":"10288_CR14","doi-asserted-by":"publisher","unstructured":"Hagerup, T.: Kernels for Edge Dominating Set: Simpler or smaller. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7464, pp. 491\u2013502. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32589-2_44","DOI":"10.1007\/978-3-642-32589-2_44"},{"key":"10288_CR15","doi-asserted-by":"publisher","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set. In: Thilikos, D.M., Woeginger, G.J. (eds.) Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7535, pp. 25\u201336. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_5","DOI":"10.1007\/978-3-642-33293-7_5"},{"issue":"2","key":"10288_CR16","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/S00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009). https:\/\/doi.org\/10.1007\/S00453-007-9133-3","journal-title":"Algorithmica"},{"issue":"3","key":"10288_CR17","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/S00224-007-1334-2","volume":"41","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory Comput. Syst. 41(3), 563\u2013587 (2007). https:\/\/doi.org\/10.1007\/S00224-007-1334-2","journal-title":"Theory Comput. Syst."},{"key":"10288_CR18","doi-asserted-by":"publisher","unstructured":"Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for Edge Domination. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5018, pp. 214\u2013225. Springer, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_20","DOI":"10.1007\/978-3-540-79723-4_20"},{"key":"10288_CR19","doi-asserted-by":"publisher","unstructured":"Xiao, M., Nagamochi, H.: A refined exact algorithm for Edge Dominating Set. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7287, pp. 360\u2013372. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29952-0_36","DOI":"10.1007\/978-3-642-29952-0_36"},{"issue":"1&2","key":"10288_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109\u2013131 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00097-3","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10288_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0002-9939-1959-0106853-5","volume":"10","author":"RZ Norman","year":"1959","unstructured":"Norman, R.Z., Rabin, M.O.: An algorithm for a minimum cover of a graph. Proceedings of the American Mathematical Society. 10(2), 315\u2013319 (1959)","journal-title":"Proceedings of the American Mathematical Society."},{"key":"10288_CR22","doi-asserted-by":"publisher","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for Vertex Cover. In: Kralovic, R., Urzyczyn, P. (eds.) Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Star\u00e1 Lesn\u00e1, Slovakia, August 28-September 1, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4162, pp. 238\u2013249. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11821069_21","DOI":"10.1007\/11821069_21"},{"key":"10288_CR23","doi-asserted-by":"publisher","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for Vertex Cover parameterized by solution size. In: Beyersdorff, O., Kant\u00e9, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France. LIPIcs, vol. 289, pp. 40\u201314018. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2024.40","DOI":"10.4230\/LIPICS.STACS.2024.40"},{"key":"10288_CR24","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10288_CR25","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"10288_CR26","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-Hitting Set. J. Discrete Algorithms. 1(1), 89\u2013102 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00009-1","journal-title":"J. Discrete Algorithms."},{"key":"10288_CR27","doi-asserted-by":"publisher","unstructured":"Bevern, R.: Towards optimal and expressive kernelization for d-Hitting Set. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Computing and Combinatorics - 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7434, pp. 121\u2013132. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32241-9_11","DOI":"10.1007\/978-3-642-32241-9_11"},{"issue":"4","key":"10288_CR28","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29\u201312960 (2016). https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"issue":"1","key":"10288_CR29","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/2390176.2390187","volume":"9","author":"G Philip","year":"2012","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for Dominating Set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 11\u201311123 (2012). https:\/\/doi.org\/10.1145\/2390176.2390187","journal-title":"ACM Trans. Algorithms"},{"issue":"23\u201324","key":"10288_CR30","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/J.IPL.2011.09.003","volume":"111","author":"M Lampis","year":"2011","unstructured":"Lampis, M.: A kernel of order $$2k-c\\log k$$ for Vertex Cover. Inf. Process. Lett. 111(23\u201324), 1089\u20131091 (2011). https:\/\/doi.org\/10.1016\/J.IPL.2011.09.003","journal-title":"Inf. Process. Lett."},{"issue":"10\u201311","key":"10288_CR31","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/J.DISC.2011.02.014","volume":"311","author":"A Soleimanfallah","year":"2011","unstructured":"Soleimanfallah, A., Yeo, A.: A kernel of order $$2k-c$$ for Vertex Cover. Discret. Math. 311(10\u201311), 892\u2013895 (2011). https:\/\/doi.org\/10.1016\/J.DISC.2011.02.014","journal-title":"Discret. Math."},{"issue":"4","key":"10288_CR32","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/J.JDA.2009.01.003","volume":"7","author":"P Damaschke","year":"2009","unstructured":"Damaschke, P., Molokov, L.: The union of minimal Hitting Sets: Parameterized combinatorial bounds and counting. J. Discrete Algorithms. 7(4), 391\u2013401 (2009). https:\/\/doi.org\/10.1016\/J.JDA.2009.01.003","journal-title":"J. Discrete Algorithms."},{"key":"10288_CR33","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for Vertex Cover parameterized by solution size (2022). arXiv:2205.08022"},{"key":"10288_CR34","doi-asserted-by":"publisher","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 326\u2013335. ACM, New York, NY, USA (1994). https:\/\/doi.org\/10.1145\/195058.195179","DOI":"10.1145\/195058.195179"},{"key":"10288_CR35","doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pp. 182\u2013191. IEEE Computer Society, Los Alamitos, CA, USA (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","DOI":"10.1109\/SFCS.1995.492475"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10288-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10288-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10288-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:24:50Z","timestamp":1784010290000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10288-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,14]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["10288"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10288-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,14]]},"assertion":[{"value":"24 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"43"}}