{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:40:23Z","timestamp":1781080823846,"version":"3.54.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Bergen Research Foundation and the University of Bergen through project \u201cBeHard\u201d"},{"name":"ERC Starting Grant PaPaAlg","award":["715744"],"award-info":[{"award-number":["715744"]}]},{"name":"ERC Starting Grant PARAPPROX","award":["306992"],"award-info":[{"award-number":["306992"]}]},{"name":"ERC Starting Grant PARAMTIGHT","award":["280152"],"award-info":[{"award-number":["280152"]}]},{"name":"Consolidator Grant SYSTEMATICGRAPH","award":["755978"],"award-info":[{"award-number":["755978"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"\n We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that\n n<\/jats:italic>\n -variable\n m<\/jats:italic>\n -clause SAT cannot be solved in time (2-\u03f5)\n \n n<\/jats:italic>\n <\/jats:sup>\n m<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n , we show that for any \u03f5 > 0:\n <\/jats:p>\n \n \u2022 I\n ndependent<\/jats:sc>\n S\n et<\/jats:sc>\n cannot be solved in time (2-\u03f5)\n \n tw(\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ,\n <\/jats:p>\n \n \u2022 D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n cannot be solved in time (3-\u03f5)\n \n tw(\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ,\n <\/jats:p>\n \n \u2022 M\n ax<\/jats:sc>\n C\n ut<\/jats:sc>\n cannot be solved in time (2-\u03f5)\n \n tw(\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ,\n <\/jats:p>\n \n \u2022 O\n dd<\/jats:sc>\n C\n ycle<\/jats:sc>\n T\n ransversal<\/jats:sc>\n cannot be solved in time (3-\u03f5)\n \n tw(\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ,\n <\/jats:p>\n \n \u2022 For any fixed\n q<\/jats:italic>\n \u2265 3,\n q<\/jats:italic>\n -C\n oloring<\/jats:sc>\n cannot be solved in time (\n q<\/jats:italic>\n -\u03f5)\n \n tw<\/jats:italic>\n (\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ,\n <\/jats:p>\n \n \u2022 P\n artition<\/jats:sc>\n I\n nto<\/jats:sc>\n T\n riangles<\/jats:sc>\n cannot be solved in time (2-\u03f5)\n \n tw<\/jats:italic>\n (\n G<\/jats:italic>\n )\n <\/jats:sup>\n |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n .\n <\/jats:p>\n Our lower bounds match the running times for the best known algorithms for the problems, up to the \u03f5 in the base.<\/jats:p>","DOI":"10.1145\/3170442","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal"],"prefix":"10.1145","volume":"14","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway, Bergen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Taramani, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.10.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690362"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884514"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_2_1_11_1","volume-title":"Proccedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC (LIPIcs)","volume":"63","author":"Borradaile Glencora","year":"2016","unstructured":"Glencora Borradaile and Hung Le . 2016 . Optimal dynamic program for r-domination problems over tree decompositions . In Proccedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC (LIPIcs) , Vol. 63 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 8:1--8:23. Glencora Borradaile and Hung Le. 2016. Optimal dynamic program for r-domination problems over tree decompositions. In Proccedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC (LIPIcs), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 8:1--8:23."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634152"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7137-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884548"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884547"},{"key":"e_1_2_1_19_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","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."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488646"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947076"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.013"},{"key":"e_1_2_1_27_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9133-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC\u201917)","volume":"10236","author":"Jaffke Lars","unstructured":"Lars Jaffke and Bart M. P. Jansen . 2017. Fine-grained parameterized complexity analysis of graph coloring problems . In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC\u201917) (Lecture Notes in Computer Science) , Vol. 10236 . 345--356. Lars Jaffke and Bart M. P. Jansen. 2017. Fine-grained parameterized complexity analysis of graph coloring problems. In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC\u201917) (Lecture Notes in Computer Science), Vol. 10236. 345--356."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634204"},{"key":"e_1_2_1_35_1","volume-title":"Algorithm Design","author":"Kleinberg Jon","unstructured":"Jon Kleinberg and \u00c9va Tardos . 2005. Algorithm Design . Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . Jon Kleinberg and \u00c9va Tardos. 2005. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_64"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.50"},{"key":"e_1_2_1_39_1","volume-title":"Can you beat treewidth?Theory Comput. 6, 1","author":"Marx D\u00e1niel","year":"2010","unstructured":"D\u00e1niel Marx . 2010. Can you beat treewidth?Theory Comput. 6, 1 ( 2010 ), 85--112. D\u00e1niel Marx. 2010. Can you beat treewidth?Theory Comput. 6, 1 (2010), 85--112."},{"key":"e_1_2_1_40_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","volume":"55","author":"Marx D\u00e1niel","year":"2016","unstructured":"D\u00e1niel Marx and Valia Mitsou . 2016 . Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) (LIPIcs), Vol. 55 . 28:1--28:15. D\u00e1niel Marx and Valia Mitsou. 2016. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) (LIPIcs), Vol. 55. 28:1--28:15."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9089-3"},{"key":"e_1_2_1_42_1","first-page":"685","article-title":"Inclusion\/exclusion meets measure and conquer","volume":"69","author":"Nederlof Jesper","year":"2014","unstructured":"Jesper Nederlof , Johan M. M. van Rooij , and Thomas C. van Dijk . 2014 . Inclusion\/exclusion meets measure and conquer . Algorithmica 69 , 3 (2014), 685 -- 740 . Jesper Nederlof, Johan M. M. van Rooij, and Thomas C. van Dijk. 2014. Inclusion\/exclusion meets measure and conquer. Algorithmica 69, 3 (2014), 685--740.","journal-title":"Algorithmica"},{"key":"e_1_2_1_43_1","volume-title":"Invitation to Fixed-parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications , Vol. 31 . Oxford University Press , Oxford . Rolf Niedermeier. 2006. Invitation to Fixed-parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873687"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.08.001"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00160-K"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645929.672845"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.12.001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915)","volume":"43","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"Virginia Vassilevska Williams . 2015 . Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk) . In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) (LIPIcs), Vol. 43 . 17--29. Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) (LIPIcs), Vol. 43. 17--29."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170442","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:57Z","timestamp":1750213617000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3170442"],"URL":"https:\/\/doi.org\/10.1145\/3170442","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2017-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}