{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:08Z","timestamp":1778807708211,"version":"3.51.4"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T00:00:00Z","timestamp":1565568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["621\/12"],"award-info":[{"award-number":["621\/12"]}]},{"DOI":"10.13039\/501100005386","name":"I-CORE","doi-asserted-by":"crossref","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-174042, CCF 1540685 and CCF 1655215"],"award-info":[{"award-number":["CCF-174042, CCF 1540685 and CCF 1655215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ISF-UGC","award":["1399\/14"],"award-info":[{"award-number":["1399\/14"]}]},{"name":"ERC-CoG","award":["772839"],"award-info":[{"award-number":["772839"]}]},{"name":"BSF","award":["2014371"],"award-info":[{"award-number":["2014371"]}]},{"name":"DIMACS\/Simons Collaboration on Bridging Continuous and Discrete Optimization"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"\n We study the parameterized complexity of approximating the\n k<\/jats:italic>\n -Dominating Set (DomSet) problem where an integer\n k<\/jats:italic>\n and a graph\n G<\/jats:italic>\n on\n n<\/jats:italic>\n vertices are given as input, and the goal is to find a dominating set of size at most\n F<\/jats:italic>\n (\n k<\/jats:italic>\n ) \u22c5\n k<\/jats:italic>\n whenever the graph\n G<\/jats:italic>\n has a dominating set of size\n k<\/jats:italic>\n . When such an algorithm runs in time\n T<\/jats:italic>\n (\n k<\/jats:italic>\n ) \u22c5 poly (\n n<\/jats:italic>\n ) (i.e., FPT-time) for some computable function\n T<\/jats:italic>\n , it is said to be an\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-\n FPT-approximation algorithm<\/jats:italic>\n for\n k<\/jats:italic>\n -DomSet. Whether such an algorithm exists is listed in the seminal book of Downey and Fellows (2013) as one of the \u201cmost infamous\u201d open problems in parameterized complexity. This work gives an almost complete answer to this question by showing the non-existence of such an algorithm under W[1] \u2260 FPT and further providing tighter running time lower bounds under stronger hypotheses. Specifically, we prove the following for every computable functions\n T<\/jats:italic>\n ,\n F<\/jats:italic>\n and every constant \u03b5 > 0:\n <\/jats:p>\n \n \u2022 Assuming W[1] \u2260 FPT, there is no\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-\n FPT-approximation algorithm<\/jats:italic>\n for\n k<\/jats:italic>\n -DomSet.\n <\/jats:p>\n \n \u2022 Assuming the Exponential Time Hypothesis (ETH), there is no\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-approximation algorithm for\n k<\/jats:italic>\n -DomSet that runs in\n T<\/jats:italic>\n (\n k<\/jats:italic>\n ) \u22c5\n n<\/jats:italic>\n \n o<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n time.\n <\/jats:p>\n \n \u2022 Assuming the Strong Exponential Time Hypothesis (SETH), for every integer\n k<\/jats:italic>\n \u2265 2, there is no\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-approximation algorithm for\n k<\/jats:italic>\n -DomSet that runs in\n T<\/jats:italic>\n (\n k<\/jats:italic>\n ) \u22c5\n n<\/jats:italic>\n \n k<\/jats:italic>\n \u2212 \u03b5\n <\/jats:sup>\n time.\n <\/jats:p>\n \n \u2022 Assuming the\n k<\/jats:italic>\n -SUM Hypothesis, for every integer\n k<\/jats:italic>\n \u2265 3, there is no\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-approximation algorithm for\n k<\/jats:italic>\n -DomSet that runs in\n T<\/jats:italic>\n (\n k<\/jats:italic>\n ) \u22c5\n n<\/jats:italic>\n \n \u2308\n k<\/jats:italic>\n \/2 \u2309 \u2212 \u03b5\n <\/jats:sup>\n time.\n <\/jats:p>\n \n Previously, only constant ratio FPT-approximation algorithms were ruled out under sf W[1] \u2260 FPT and (log\n 1\/4<\/jats:sup>\n &minus \u03b5\n k<\/jats:italic>\n )-FPT-approximation algorithms were ruled out under ETH [Chen and Lin, FOCS 2016]. Recently, the non-existence of an\n F<\/jats:italic>\n (\n k<\/jats:italic>\n )-FPT-approximation algorithm for any function\n F<\/jats:italic>\n was shown under Gap-ETH [Chalermsook et\u00a0al., FOCS 2017]. Note that, to the best of our knowledge, no running time lower bound of the form\n n<\/jats:italic>\n \n &delta\n k<\/jats:italic>\n <\/jats:sup>\n for any absolute constant \u03b4 > 0 was known before even for any constant factor inapproximation ratio.\n <\/jats:p>\n Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud\u00a0et\u00a0al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well-studied problem or a variant of one; this allows us to easily apply known techniques to solve them.<\/jats:p>","DOI":"10.1145\/3325116","type":"journal-article","created":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T14:41:50Z","timestamp":1565707310000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["On the Parameterized Complexity of Approximating Dominating Set"],"prefix":"10.1145","volume":"66","author":[{"given":"Karthik C.","family":"S.","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, Yangpu, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.12"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214074"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150334.1150336"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700375944"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_12_1","unstructured":"Eli Ben-Sasson Alessandro Chiesa Ariel Gabizon Michael Riabzev and Nicholas Spooner. 2016. Short interactive oracle proofs with constant query complexity via composition and sumcheck. Electr. Coll. Comput. Complex. 23 (2016) 46:1--46:38. Eli Ben-Sasson Alessandro Chiesa Ariel Gabizon Michael Riabzev and Nicholas Spooner. 2016. Short interactive oracle proofs with constant query complexity via composition and sumcheck. Electr. Coll. Comput. Complex. 23 (2016) 46:1--46:38."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2901294"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1718470.1718480"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.74"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_18_1","volume-title":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201916)","author":"Charikar Moses","year":"2016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.73"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_10"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.61"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Cormode Graham","year":"2008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer. Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_28_1","unstructured":"Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electr. Coll. Comput. Complex. 23 (2016) 128:1--128:15. Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electr. Coll. Comput. Complex. 23 (2016) 128:1--128:15."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Rodney G. Downey and Michael R. Fellows. 1995. Parameterized Computational Feasibility. Birkh\u00e4user Boston Boston MA 219--244. Rodney G. Downey and Michael R. Fellows. 1995. Parameterized Computational Feasibility. Birkh\u00e4user Boston Boston MA 219--244.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer. Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_11"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0147"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1373317"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918)","author":"Goldreich Oded"},{"key":"e_1_2_1_42_1","unstructured":"Mohammad Taghi Hajiaghayi Rohit Khandekar and Guy Kortsarz. 2013. The foundations of fixed parameter inapproximability. CoRR abs\/1310.2711 (2013). http:\/\/arxiv.org\/abs\/1310.2711 Mohammad Taghi Hajiaghayi Rohit Khandekar and Guy Kortsarz. 2013. The foundations of fixed parameter inapproximability. CoRR abs\/1310.2711 (2013). http:\/\/arxiv.org\/abs\/1310.2711"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_2_1_48_1","unstructured":"Viggo Kann. 1992. On the Approximability of NP-complete Optimization Problems. Ph.D. Dissertation. Royal Institute of Technology. Viggo Kann. 1992. On the Approximability of NP-complete Optimization Problems. Ph.D. Dissertation. Royal Institute of Technology."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_50_1","unstructured":"Swastik Kopparty. 2017. Personal communication. Swastik Kopparty. 2017. Personal communication."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY. Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1803907"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201911)","author":"Liang Guanfeng"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722170"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP'19)","volume":"132","author":"Lin Bingkai","year":"2019"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_58_1","unstructured":"Pasin Manurangsi and Prasad Raghavendra. 2016. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986 (2016). http:\/\/arxiv.org\/abs\/1607.02986 Pasin Manurangsi and Prasad Raghavendra. 2016. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986 (2016). http:\/\/arxiv.org\/abs\/1607.02986"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/110829660"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of Combinatorics, Paul Erdos Is Eighty. 301--315","author":"Nisan Noam","year":"1994"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873687"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095158"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_69_1","unstructured":"Aviad Rubinstein. 2017. Personal communication. Aviad Rubinstein. 2017. Personal communication."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.945244"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237991"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225138"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3078-3"},{"key":"e_1_2_1_77_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201915)","author":"Weinstein Omri"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325116","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325116","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:16Z","timestamp":1750204456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,12]]},"references-count":79,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3325116"],"URL":"https:\/\/doi.org\/10.1145\/3325116","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,12]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}