{"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":1784110304136,"version":"3.55.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC) consolidator","award":["725978 SYSTEMATICGRAPH"],"award-info":[{"award-number":["725978 SYSTEMATICGRAPH"]}]},{"name":"Austrian Science Fund","award":["10.55776\/Y1329"],"award-info":[{"award-number":["10.55776\/Y1329"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets \u03c2, \u03c1 of non-negative integers, a (\u03c3, \u03c1)-set of a graph\n            <jats:italic>G<\/jats:italic>\n            is a set\n            <jats:italic>S<\/jats:italic>\n            of vertices such that\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(|N(u)\\cap S|\\in \\sigma\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for every\n            <jats:italic>u<\/jats:italic>\n            \u2208\n            <jats:italic>S<\/jats:italic>\n            , and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(|N(v)\\cap S|\\in \\rho\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for every\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(v\\not\\in S\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . The problem of finding a (\u03c3, \u03c1)-set (of a certain size) unifies common problems like\n            <jats:sc>Independent Set<\/jats:sc>\n            ,\n            <jats:sc>Dominating Set<\/jats:sc>\n            ,\n            <jats:sc>Independent Dominating Set<\/jats:sc>\n            , and many others.\n          <\/jats:p>\n          <jats:p>\n            In an accompanying article, it is proven that, for all pairs of finite or cofinite sets (\u03c3, \u03c1), there is an algorithm that counts (\u03c3, \u03c1)-sets in time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((c_{\\sigma ,\\rho })^{\\sf tw}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (if a tree decomposition of width\n            <jats:monospace>tw<\/jats:monospace>\n            is given in the input). Here, \u03c2, \u03c1 is a constant with an intricate dependency on \u03c2 and \u03c1. Despite this intricacy, we show that the algorithms in the accompanying article are most likely optimal, i.e., for any pair (\u03c3, \u03c1) of finite or cofinite sets where the problem is non-trivial, and any \u025b &gt; 0, a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((c_{\\sigma ,\\rho }-\\varepsilon)^{\\sf tw}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -algorithm counting the number of (\u03c3, \u03c1)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets \u03c2 and \u03c1, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well.\n          <\/jats:p>","DOI":"10.1145\/3708509","type":"journal-article","created":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T11:07:26Z","timestamp":1738235246000},"page":"1-101","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 Part II: Hardness Results"],"prefix":"10.1145","volume":"17","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, United States"}],"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, Tokyo Japan and The Graduate University for Advanced Studies, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6_110"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.008"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.70"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2018.27"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Jacob Focke D\u00e1niel Marx Fionn Mc Inerney Daniel Neuen Govind S. Sankar Philipp Schepper and Philip Wellnitz. 2023. Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs. Part I: Algorithmic Results. (2023). DOI:DOI:10.48550\/arXiv.2211.04278","DOI":"10.48550\/arXiv.2211.04278"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.22"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3039243"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.11.002"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.95"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2022.22"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.74"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1320146"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-53832-1_28"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/640186.640195"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-42071-0_18"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708509","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708509","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:55Z","timestamp":1750295395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708509"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,25]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3708509"],"URL":"https:\/\/doi.org\/10.1145\/3708509","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,25]]},"assertion":[{"value":"2023-12-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}