{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T18:33:31Z","timestamp":1781721211878,"version":"3.54.5"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["314528"],"award-info":[{"award-number":["314528"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004329","name":"Slovenian Research and Innovation Agency","doi-asserted-by":"crossref","award":["I0-0035, research program P1-0285 and research projects (J1-3003, J1-4008, J1-4084, J1-60012, and N1-0370"],"award-info":[{"award-number":["I0-0035, research program P1-0285 and research projects (J1-3003, J1-4008, J1-4084, J1-60012, and N1-0370"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"crossref"}]},{"name":"research program CogniCom","award":["0013103"],"award-info":[{"award-number":["0013103"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n                    The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several\n                    <jats:monospace>NP<\/jats:monospace>\n                    -hard graph problems, like maximum-weight independent set, can be solved in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{\\mathcal{O}(k)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    if the input\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -vertex graph is given together with a tree decomposition of independence number\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Yolov, in SODA 2018, gave an algorithm that, given an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -vertex graph\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and an integer\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{\\mathcal{O}(k^{3})}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    either constructs a tree decomposition of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    whose independence number is\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(k^{3})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    or correctly reports that the tree-independence number of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is larger than\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{\\mathcal{O}(k^{2})}n^{\\mathcal{O}(k)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and either outputs a tree decomposition of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    with independence number at most\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(8k\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    or determines that the tree-independence number of\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is larger than\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . This implies\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(2^{\\mathcal{O}(k^{2})}n^{\\mathcal{O}(k)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -time algorithms for various problems, like maximum-weight independent set, parameterized by the tree-independence number\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    without needing the decomposition as an input. Assuming Gap-ETH, an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{\\Omega(k)}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    factor in the running time is unavoidable for any approximation algorithm for the tree-independence number.\n                  <\/jats:p>\n                  <jats:p>\n                    Our second result is that the exact computation of the tree-independence number is\n                    <jats:monospace>para-NP<\/jats:monospace>\n                    -hard: We show that for every constant\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\geq 4\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    it is\n                    <jats:monospace>NP<\/jats:monospace>\n                    -complete to decide whether a given graph has the tree-independence number at most\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3767730","type":"journal-article","created":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T13:17:36Z","timestamp":1758028656000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Computing Tree Decompositions with Small Independence\u00a0Number"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9522-3770","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Dallard","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Fribourg, Fribourg, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-6515","authenticated-orcid":false,"given":"Tuukka","family":"Korhonen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Kobenhavn, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8222-8097","authenticated-orcid":false,"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[{"name":"IAM and FAMNIT, University of Primorska, Koper, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"issue":"4","key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1002\/jgt.23104","article-title":"Tree independence number. I. (even hole, diamond, pyramid)-free graphs","volume":"106","author":"Abrishami T.","year":"2024","unstructured":"T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, and K. Vu\u0161kovi\u0107. 2024. Tree independence number. I. (even hole, diamond, pyramid)-free graphs. Journal of Graph Theory 106, 4 (2024), 923\u2013943.","journal-title":"Journal of Graph Theory"},{"key":"e_1_3_3_3_2","volume-title":"Width Functions for Hypertree Decompositions","author":"Adler I.","year":"2006","unstructured":"I. Adler. 2006. Width Functions for Hypertree Decompositions. Ph.D thesis, Albert-Ludwigs-Universit\u00e4t Freiburg im Breisgau."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"issue":"1","key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","article-title":"Precoloring extension. I. Interval graphs","volume":"100","author":"B\u00edr\u00f3 M.","year":"1992","unstructured":"M. B\u00edr\u00f3, M. Hujter, and Z. Tuza. 1992. Precoloring extension. I. Interval graphs. Discrete Mathematics 100, 1\u20133 (1992), 267\u2013279.","journal-title":"Discrete Mathematics"},{"issue":"2","key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/130947374","article-title":"A  \\(c^{k}n\\)  5-approximation algorithm for treewidth","volume":"45","author":"Bodlaender H. L.","year":"2016","unstructured":"H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk. 2016. A \\(c^{k}n\\) 5-approximation algorithm for treewidth. SIAM Journal on Computing 45, 2 (2016), 317\u2013378.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_7_2","first-page":"574","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bodlaender H. L.","year":"1998","unstructured":"H. L. Bodlaender, J. Gustedt, and J. A. Telle. 1998. Linear-time register allocation for a fixed number of registers. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. H. J. Karloff (Ed.), ACM\/SIAM, San Francisco, CA, 574\u2013583."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166869"},{"issue":"2","key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1137\/19M1299001","article-title":"Kernelization of graph hamiltonicity: Proper  \\( H \\) -graphs","volume":"35","author":"Chaplick S.","year":"2021","unstructured":"S. Chaplick, F. V. Fomin, P. A. Golovach, D. Knop, and P. Zeman. 2021. Kernelization of graph hamiltonicity: Proper \\( H \\) -graphs. SIAM Journal on Discrete Mathematics 35, 2 (2021), 840\u2013892.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"11","key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"3281","DOI":"10.1007\/s00453-021-00846-3","article-title":"On  \\( H \\) -topological intersection graphs","volume":"83","author":"Chaplick S.","year":"2021","unstructured":"S. Chaplick, M. T\u00f6pfer, J. Voborn\u00edk, and P. Zeman. 2021. On \\( H \\) -topological intersection graphs. Algorithmica 83, 11 (2021), 3281\u20133318.","journal-title":"Algorithmica"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","unstructured":"S. Chaplick and P. Zeman. 2017. Combinatorial problems on \\( H \\) -graphs. Electronic Notes in Discrete Mathematics 61 (2017) 223\u2013229.","DOI":"10.1016\/j.endm.2017.06.042"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","unstructured":"M. Chudnovsky P. Gartland S. Hajebi D. Lokshtanov and S. Spirkl. 2025. Tree independence number IV. Even-hole-free graphs. In Proceedings of the 2025 Annual {ACM-SIAM} Symposium on Discrete Algorithms {SODA} 2025 New Orleans LA USA January 12\u201315 2025. Yossi Azar and Debmalya Panigrahi (Eds.) SIAM 4444\u20134461. DOI: 10.1137\/1.9781611978322.151","DOI":"10.1137\/1.9781611978322.151"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","unstructured":"M. Chudnovsky S. Hajebi D. Lokshtanov and S. Spirkl. 2026. Tree independence number II. Three-path-configurations. Journal of Combinatorial Theory Series B 176 (2026) 74\u201396. DOI: 10.1016\/j.jctb.2025.08.003","DOI":"10.1016\/j.jctb.2025.08.003"},{"key":"e_1_3_3_14_2","unstructured":"M. Chudnovsky S. Hajebi and N. Trotignon. 2024. Tree independence number III. Thetas prisms and stars. arXiv:2406.13053. Retrieved from https:\/\/arxiv.org\/abs\/2406.13053"},{"key":"e_1_3_3_15_2","unstructured":"M. Chudnovsky and N. Trotignon. 2024. On treewidth and maximum cliques. arXiv:2405.07471. Retrieved from https:\/\/arxiv.org\/abs\/2405.07471"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","unstructured":"C. Dallard M. Krnc O. Joung Kwon M. Milani\u010d A. Munaro K. \u0160torgel and S. Wiederrecht. 2024. Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star. arXiv:2402.11222. Retrieved from https:\/\/arxiv.org\/abs\/2402.11222","DOI":"10.1016\/j.jctb.2023.10.006"},{"key":"e_1_3_3_19_2","first-page":", 92","volume-title":"Graph-Theoretic Concepts in Computer Science - 46th International Workshop (WG \u201920)","author":"Dallard C.","year":"2020","unstructured":"C. Dallard, M. Milani\u010d, and K. \u0160torgel. 2020. Treewidth versus clique number in graph classes with a forbidden structure. In Graph-Theoretic Concepts in Computer Science - 46th International Workshop (WG \u201920). I. Adler and H. M\u00fcller (Eds.), Lecture Notes in Computer Science, Vol. 12301, Springer, 92\u2013105."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.10.006"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1352119"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.03.005"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1320870"},{"issue":"6","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","article-title":"Subexponential parameterized algorithms on graphs of bounded genus and  \\( H \\) -minor-free graphs","volume":"52","author":"Demaine E. D.","year":"2005","unstructured":"E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. 2005. Subexponential parameterized algorithms on graphs of bounded genus and \\( H \\) -minor-free graphs. Journal of the ACM 52, 6 (2005), 866\u2013893.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_25_2","unstructured":"I. Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity TR16\u2013128."},{"issue":"1","key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.37236\/1799","article-title":"Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard","volume":"11","author":"Farrugia A.","year":"2004","unstructured":"A. Farrugia. 2004. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. The Electronic Journal of Combinatorics 11, 1 (2004), 46\u201349.","journal-title":"The Electronic Journal of Combinatorics"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00822-x"},{"issue":"9","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"2432","DOI":"10.1007\/s00453-020-00692-9","article-title":"On the tractability of optimization problems on  \\( H \\) -graphs","volume":"82","author":"Fomin F. V.","year":"2020","unstructured":"F. V. Fomin, P. A. Golovach, and J.-F. Raymond. 2020. On the tractability of optimization problems on \\( H \\) -graphs. Algorithmica 82, 9 (2020), 2432\u20132473.","journal-title":"Algorithmica"},{"issue":"2","key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"10:1","DOI":"10.1145\/3154833","article-title":"Excluded grid minors and efficient polynomial-time approximation schemes","volume":"65","author":"Fomin F. V.","year":"2018","unstructured":"F. V. Fomin, D. Lokshtanov, and S. Saurabh. 2018. Excluded grid minors and efficient polynomial-time approximation schemes. Journal of the ACM 65, 2 (2018), 10:1\u201310:44.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_31_2","first-page":", 34:1","volume-title":"Proceedings of the 39th International Symposium on Computational Geometry (SoCG \u201923)","author":"Galby E.","year":"2023","unstructured":"E. Galby, A. Munaro, and S. Yang. 2023. Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs. In Proceedings of the 39th International Symposium on Computational Geometry (SoCG \u201923). E. W. Chambers and J. Gudmundsson (Eds.), LIPIcs, Vol. 258, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 34:1\u201334:15."},{"key":"e_1_3_3_32_2","unstructured":"E. Galby A. Munaro and S. Yang. 2024. Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs. arXiv:2402.18352. Retrieved from https:\/\/arxiv.org\/abs\/2402.18352"},{"key":"e_1_3_3_33_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_3_34_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980","unstructured":"M. C. Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"issue":"1","key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0012-365X(00)00204-1","article-title":"Representing graphs by disks and balls (a survey of recognition-complexity results)","volume":"229","author":"Hlinen\u00fd P.","year":"2001","unstructured":"P. Hlinen\u00fd and J. Kratochv\u00edl. 2001. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics 229, 1\u20133 (2001), 101\u2013124.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00971-7"},{"key":"e_1_3_3_38_2","first-page":"6:1","volume-title":"Proceedings of the 37th Computational Complexity Conference (CCC \u201922)","volume":"234","author":"Karthik C. S.","year":"2022","unstructured":"C. S. Karthik and S. Khot. 2022. Almost polynomial factor inapproximability for parameterized \\( k \\) -clique. In Proceedings of the 37th Computational Complexity Conference (CCC \u201922). S. Lovett (Ed.), LIPIcs, Vol. 234, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:21."},{"key":"e_1_3_3_39_2","first-page":"85:1","volume-title":"Proceedings of the 32nd Annual European Symposium on Algorithms (ESA \u201924)","author":"Lima P. T.","year":"2024","unstructured":"P. T. Lima, M. Milani\u010d, P. Mur\u0161i\u010d, K. Okrasa, P. Rza\u00b8\u017cewski, and K. \u0160torgel. 2024. Tree decompositions meet induced matchings: Beyond max weight independent set. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA \u201924). T. Chan, J. Fischer, J. Iacono, and G. Herman (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 308, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 85:1\u201385:17."},{"key":"e_1_3_3_40_2","first-page":", 1749","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201921)","author":"Lin B.","unstructured":"B. Lin. 2021. Constant approximating \\( k \\) -clique is W[1]-hard. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201921). S. Khuller and V. V. Williams (Eds.), ACM, 1749\u20131756."},{"key":"e_1_3_3_41_2","first-page":"2031","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Lokshtanov D.","year":"2022","unstructured":"D. Lokshtanov, F. Panolan, S. Saurabh, J. Xue, and M. Zehavi. 2022. Subexponential parameterized algorithms on disk graphs (extended abstract). In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2031."},{"key":"e_1_3_3_42_2","first-page":"78:1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917)","volume":"80","author":"Manurangsi P.","unstructured":"P. Manurangsi and P. Raghavendra. 2017. A birthday repetition theorem and complexity of approximating dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP \u201917). I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl (Eds.), LIPIcs, Vol. 80, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 78:1\u201378:15."},{"issue":"6","key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/2535926","article-title":"Tractable hypergraph properties for constraint satisfaction and conjunctive queries","volume":"60","author":"Marx D.","year":"2013","unstructured":"D. Marx. 2013. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM 60, 6, Article 42 (2013), 51.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_44_2","first-page":"189","volume-title":"Proceedings of the Treewidth, Kernels, and Algorithms\u2014Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday","volume":"12160","author":"Pilipczuk M.","year":"2020","unstructured":"M. Pilipczuk. 2020. Computing tree decompositions. In Proceedings of the Treewidth, Kernels, and Algorithms\u2014Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. F. V. Fomin, S. Kratsch, and E. J. van Leeuwen (Eds.), Lecture Notes in Computer Science, Vol. 12160, Springer, 189\u2013213."},{"issue":"1","key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/S0196-6774(03)00048-8","article-title":"Robust algorithms for restricted domains","volume":"48","author":"Raghavan V.","year":"2023","unstructured":"V. Raghavan and J. P. Spinrad. 2023. Robust algorithms for restricted domains. Journal of Algorithms 48, 1 (2023), 160\u2013172.","journal-title":"Journal of Algorithms"},{"key":"e_1_3_3_46_2","unstructured":"X. Ren. 2021. A survey on parameterized inapproximability: \\( k \\) -clique \\( k \\) -setcover and more. arXiv:2112.04669. Retrieved from https:\/\/arxiv.org\/abs\/2112.04669"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/3-540-46784-X_16","volume-title":"Proceedings of the Graph-Theoretic Concepts in Computer Science, 25th International Workshop (WG \u201999)","volume":"1665","author":"Skodinis K.","year":"1999","unstructured":"K. Skodinis. 1999. Efficient analysis of graphs with small minimal separators. In Proceedings of the Graph-Theoretic Concepts in Computer Science, 25th International Workshop (WG \u201999). P. Widmayer, G. Neyer, and S. J. Eidenbenz (Eds.), Lecture Notes in Computer Science, Vol. 1665, Springer, 155\u2013166."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"},{"key":"e_1_3_3_51_2","first-page":"219","volume-title":"Proceedings of the 2th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Yolov N.","year":"2018","unstructured":"N. Yolov. 2018. Minor-matching hypertree width. In Proceedings of the 2th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 219\u2013233."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T13:29:30Z","timestamp":1762781370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3767730"],"URL":"https:\/\/doi.org\/10.1145\/3767730","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,10]]},"assertion":[{"value":"2024-09-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}