{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:11:44Z","timestamp":1784110304008,"version":"3.55.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"\n We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets\n \n \\(\\sigma,\\rho\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of non-negative integers, a\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -set<\/jats:italic>\n of a graph\n G<\/jats:italic>\n is a set\n S<\/jats:italic>\n of vertices such that\n \n \\(|N(u)\\cap S|\\in\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for every\n \n \\(u\\in S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and\n \n \\(|N(\\!\\textit{v})\\cap S|\\in\\rho\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for every\n \n \\(\\textit{v}\\not\\in S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The problem of finding a\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -set (of a certain size) unifies standard problems, such as\n Independent Set<\/jats:sc>\n ,\n Dominating Set<\/jats:sc>\n ,\n Independent Dominating Set<\/jats:sc>\n , and many others.\n <\/jats:p>\n \n For all pairs of finite or cofinite sets\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we determine (under standard complexity assumptions) the best possible value\n \n \\(c_{\\sigma,\\rho}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that there is an algorithm that counts\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -sets in time\n \n \\(c_{\\sigma,\\rho}^{\\textsf{tw}}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (if a tree decomposition of width\n \n \\(\\textsf{tw}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is given in the input). Let\n \n \\(s_{{\\rm top}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denote the largest element of\n \n \\(\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if\n \n \\(\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is finite, or the largest missing integer\n \n \\(+1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if\n \n \\(\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is cofinite;\n \n \\(r_{{\\rm top}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is defined analogously for\n \n \\(\\rho\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Surprisingly,\n \n \\(c_{\\sigma,\\rho}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is often significantly smaller than the natural bound\n \n \\(s_{{\\rm top}}+r_{{\\rm top}}+2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n achieved by existing algorithms. Toward defining\n \n \\(c_{\\sigma,\\rho}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we say that\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is\n \n \\({\\mathrm{m}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -structured if there is a pair\n \n \\((\\alpha,\\beta)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that every integer in\n \n \\(\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n equals\n \n \\(\\alpha\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n mod\n \n \\({\\mathrm{m}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and every integer in\n \n \\(\\rho\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n equals\n \n \\(\\beta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n mod\n \n \\({\\mathrm{m}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Then, setting\n \n \n \u2014<\/jats:label>\n \n \n \\(c_{\\sigma,\\rho}=s_{{\\rm top}}+r_{{\\rm top}}+2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is not\n \n \\({\\mathrm{m}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -structured for any\n \n \\({\\mathrm{m}}\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n \n \\(c_{\\sigma,\\rho}=\\max\\{s_{{\\rm top}},r_{{\\rm top}}\\}+2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is 2-structured, but not\n \n \\({\\mathrm{m}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -structured for any\n \n \\({\\mathrm{m}}\\geq 3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and\n \n \\(s_{{\\rm top}}=r_{{\\rm top}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is even, and we count the number of edges between\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n \n \\(c_{\\sigma,\\rho}=\\max\\{s_{{\\rm top}},r_{{\\rm top}}\\}+1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , otherwise,\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n \n we provide algorithms counting\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -sets in time\n \n \\(c_{\\sigma,\\rho}^{\\textsf{tw}}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . For example, for the\n Exact Independent Dominating Set<\/jats:sc>\n problem (also known as\n Perfect Code<\/jats:sc>\n ) corresponding to\n \n \\(\\sigma=\\{0\\}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\rho=\\{1\\}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , this improves the\n \n \\(3^{\\textsf{tw}}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n algorithm of van Rooij to\n \n \\(2^{\\textsf{tw}}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Despite the unusually delicate definition of\n \n \\(c_{\\sigma,\\rho}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of finite or cofinite sets where the problem is non-trivial, and any\n \n \\(\\varepsilon > 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a\n \n \\((c_{\\sigma,\\rho}-\\varepsilon)^{\\textsf{tw}}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -algorithm counting the number of\n \n \\((\\sigma,\\rho)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets\n \n \\(\\sigma\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\rho\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , these lower bounds also extend to the decision version, and hence, our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets.\n <\/jats:p>","DOI":"10.1145\/3731452","type":"journal-article","created":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T12:05:52Z","timestamp":1745237152000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs\u2014Part I: Algorithmic Results"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":false,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5634-9506","authenticated-orcid":false,"given":"Fionn","family":"Mc Inerney","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4940-0318","authenticated-orcid":false,"given":"Daniel","family":"Neuen","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7443-9599","authenticated-orcid":false,"given":"Govind S.","family":"Sankar","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5810-7949","authenticated-orcid":false,"given":"Philipp","family":"Schepper","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6482-8478","authenticated-orcid":false,"given":"Philip","family":"Wellnitz","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, and The Graduate University for Advanced Studies, SOKENDAI, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_52"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_5_2","first-page":"33","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM\/SIAM, 33\u201341. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=314613.314632"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1552442669"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90016-2"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6_110"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.022"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.009"},{"key":"e_1_3_2_16_2","unstructured":"Mathieu Chapelle. 2010. Parameterized complexity of generalized domination problems on bounded tree-width graphs. arXiv:1004.2642. Retrieved from https:\/\/arxiv.org\/abs\/1004.2642"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.70"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2018.27"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","unstructured":"Jacob Focke D\u00e1niel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper and Philip Wellnitz. 2025. Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. Part II: Hardness results. ACM Transactions on Computation Theory 17 2 (2025) 1\u2013101. DOI: 10.1145\/370850","DOI":"10.1145\/370850"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch140"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3640814"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.03.023"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9418-9"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3039243"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.11.012"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00124-9"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2018.6"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.11.002"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.7"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3390887"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.95"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-024-01265-W"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.74"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1320146"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-53832-1_28"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"issue":"1","key":"e_1_3_2_47_2","first-page":"157","article-title":"Complexity of domination-type problems in graphs","volume":"1","author":"Telle Jan Arne","year":"1994","unstructured":"Jan Arne Telle. 1994. Complexity of domination-type problems in graphs. Nord. J. Comput. 1, 1 (1994), 157\u2013171.","journal-title":"Nord. J. Comput"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57155-8_284"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-42071-0_18"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79416-3_27"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,28]],"date-time":"2025-07-28T11:45:29Z","timestamp":1753703129000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,28]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3731452"],"URL":"https:\/\/doi.org\/10.1145\/3731452","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,28]]},"assertion":[{"value":"2023-12-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}