{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:49:56Z","timestamp":1760240996965,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872092"],"award-info":[{"award-number":["61872092"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-     AC  0     and the k-DominatingSet (k-DomSet) problem could not be computed by para-     AC  0     circuits. It is natural to ask whether the     f ( k )    -approximation of the k-DomSet problem is in para-     AC  0     for some computable function f. Very recently it was proved that assuming     W [ 1 ] \u2260 FPT     , the k-DomSet problem cannot be     f ( k )    -approximated by FPT algorithms for any computable function f by S., Laekhanukit and Manurangsi and Lin, seperately. We observe that the constructions used in Lin\u2019s work can be carried out using constant-depth circuits, and thus we prove that para-     AC  0     circuits could not approximate this problem with ratio     f ( k )     for any computable function f. Moreover, under the hypothesis that the 3-CNF-SAT problem cannot be computed by constant-depth circuits of size     2  \u03b5 n      for some     \u03b5 &gt; 0    , we show that constant-depth circuits of size     n  o ( k )      cannot distinguish graphs whose dominating numbers are either \u2264k or &gt;        log n   3 log log n      1 \/ k     . However, we find that the hypothesis may be hard to settle by showing that it implies     NP \u2288  NC 1     .<\/jats:p>","DOI":"10.3390\/a12110230","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T10:49:07Z","timestamp":1572864547000},"page":"230","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Inapproximability of k-DominatingSet for Parameterized \r\n        \r\n          \r\n            \r\n              \r\n                AC\r\n              \r\n              0\r\n            \r\n          \r\n        \r\n       Circuits \u2020"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7525-692X","authenticated-orcid":false,"given":"Wenxing","family":"Lai","sequence":"first","affiliation":[{"name":"Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 201203, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Miller, R.E., Thatcher, J.W., and Bohlinger, J.D. (1972). Reducibility among Combinatorial Problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"41:1","DOI":"10.1145\/2925416","article-title":"On Problems As Hard As CNF-SAT","volume":"12","author":"Cygan","year":"2016","journal-title":"ACM Trans. Algorithms"},{"key":"ref_3","unstructured":"Krauthgamer, R., and Trabelsi, O. (2019, January 13\u201316). The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation Algorithms for Combinatorial Problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0097-3165(74)90062-4","article-title":"Two Combinatorial Covering Theorems","volume":"16","author":"Stein","year":"1974","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","article-title":"On the Ratio of Optimal Integral and Fractional Covers","volume":"13","year":"1975","journal-title":"Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A Greedy Heuristic for the Set-Covering Problem","volume":"4","author":"Chvatal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1006\/jagm.1997.0887","article-title":"A Tight Analysis of the Greedy Algorithm for Set Cover","volume":"25","year":"1997","journal-title":"J. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","article-title":"The Bidimensionality Theory and Its Algorithmic Applications 1","volume":"51","author":"Demaine","year":"2008","journal-title":"Comput. J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the Hardness of Approximating Minimization Problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Raz, R., and Safra, S. (1997, January 4\u20136). A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC \u201997), El Paso, TX, USA.","DOI":"10.1145\/258533.258641"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A Threshold of ln n for Approximating Set Cover","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/1150334.1150336","article-title":"Algorithmic Construction of Sets for k-restrictions","volume":"2","author":"Alon","year":"2006","journal-title":"ACM Trans. Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/978-3-642-32512-0_24","article-title":"The Projection Games Conjecture and the NP-Hardness of lnn-Approximating Set-Cover","volume":"Volume 7408","author":"Hutchison","year":"2012","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"},{"key":"ref_15","unstructured":"Dinur, I., and Steurer, D. (June, January 31). Analytical Approach to Parallel Repetition. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC \u201914), New York, NY, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., and Trevisan, L. (2017, January 15\u201317). From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2017.74"},{"key":"ref_17","unstructured":"Laekhanukit, B., and Manurangsi, P. (2018, January 25\u201329). On the Parameterized Complexity of Approximating Dominating Set. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA."},{"key":"ref_18","unstructured":"Lin, B. (2019, January 8\u201312). A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, Circuits, and the Polynomial-Time Hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Syst. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-Formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Ann. Pure Appl. Log."},{"key":"ref_21","first-page":"1","article-title":"Almost Optimal Lower Bounds for Small Depth Circuits","volume":"Volume 58","author":"Faliszewski","year":"2016","journal-title":"Leibniz International Proceedings in Informatics (LIPIcs), Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)"},{"key":"ref_22","unstructured":"Williams, R. (June, January 31). New Algorithms and Lower Bounds for Circuits with Linear Threshold Gates. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC \u201914), New York, NY, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/2559903","article-title":"Nonuniform ACC Circuit Lower Bounds","volume":"61","author":"Williams","year":"2014","journal-title":"J. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Murray, C., and Williams, R. (2018, January 25\u201329). Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201918), Los Angeles, CA, USA.","DOI":"10.1145\/3188745.3188910"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Rossman, B. (2008, January 17\u201320). On the Constant-depth Complexity of k-clique. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC \u201908), Victoria, BC, Canada.","DOI":"10.1145\/1374376.1374480"},{"key":"ref_26","first-page":"1","article-title":"Some Lower Bounds in Parameterized AC0","volume":"Volume 58","author":"Faliszewski","year":"2016","journal-title":"Leibniz International Proceedings in Informatics (LIPIcs), Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","article-title":"On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness","volume":"71","author":"Elberfeld","year":"2015","journal-title":"Algorithmica"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer. Monographs in Computer Science.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","article-title":"Approximation Hardness of Dominating Set Problems in Bounded Degree Graphs","volume":"206","year":"2008","journal-title":"Inf. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Lai, W. (May, January 29). The Inapproximability of k-DominatingSet for Parameterized AC0 Circuits. Proceedings of the Thirteenth International Frontiers of Algorithmics Workshop (FAW 2019), Sanya, China.","DOI":"10.1007\/978-3-030-18126-0_12"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1137\/16M1067767","article-title":"Upper Bounds on the Size of Covering Arrays","volume":"31","author":"Sarkar","year":"2017","journal-title":"SIAM J. Discret. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","article-title":"Families of k-independent sets","volume":"6","author":"Kleitman","year":"1973","journal-title":"Discret. Math."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Charikar, M. (2010). On the Possibility of Faster SAT Algorithms. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973075"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/230\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:31:46Z","timestamp":1760189506000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,4]]},"references-count":33,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2019,11]]}},"alternative-id":["a12110230"],"URL":"https:\/\/doi.org\/10.3390\/a12110230","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,11,4]]}}}