{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:33:01Z","timestamp":1778643181758,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T00:00:00Z","timestamp":1552003200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            We give a new general approach for designing exact exponential-time algorithms for\n            <jats:italic>subset problems<\/jats:italic>\n            . In a subset problem the input implicitly describes a family of sets over a universe of size\n            <jats:italic>n<\/jats:italic>\n            and the task is to determine whether the family contains at least one set. A typical example of a subset problem is W\n            <jats:sc>EIGHTED<\/jats:sc>\n            <jats:italic>d<\/jats:italic>\n            -SAT. Here, the input is a CNF-formula with clauses of size at most\n            <jats:italic>d<\/jats:italic>\n            , and an integer\n            <jats:italic>W<\/jats:italic>\n            . The universe is the set of variables and the variables have integer weights. The family contains all the subsets\n            <jats:italic>S<\/jats:italic>\n            of variables such that the total weight of the variables in\n            <jats:italic>S<\/jats:italic>\n            does not exceed\n            <jats:italic>W<\/jats:italic>\n            and setting the variables in\n            <jats:italic>S<\/jats:italic>\n            to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on \u201cmonotone local search,\u201d where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset\n            <jats:italic>X<\/jats:italic>\n            of the universe and an integer\n            <jats:italic>k<\/jats:italic>\n            . The task is to determine whether one can add at most\n            <jats:italic>k<\/jats:italic>\n            elements to\n            <jats:italic>X<\/jats:italic>\n            to obtain a set in the (implicitly defined) family. Our main result is that a\n            <jats:italic>\n              c\n              <jats:sup>k<\/jats:sup>\n              n\n              <jats:sup>O(1)<\/jats:sup>\n            <\/jats:italic>\n            time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time\n            <jats:italic>O<\/jats:italic>\n            ((2\u22121\/\n            <jats:italic>c<\/jats:italic>\n            )\n            <jats:sup>n<\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            In many cases, the extension problem can be reduced to simply finding a solution of size at most\n            <jats:italic>k<\/jats:italic>\n            . Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including\n            <jats:italic>d<\/jats:italic>\n            -H\n            <jats:sc>ITTING<\/jats:sc>\n            S\n            <jats:sc>ET<\/jats:sc>\n            , F\n            <jats:sc>EEDBACK<\/jats:sc>\n            V\n            <jats:sc>ERTEX<\/jats:sc>\n            S\n            <jats:sc>ET<\/jats:sc>\n            , N\n            <jats:sc>ODE<\/jats:sc>\n            U\n            <jats:sc>NIQUE<\/jats:sc>\n            L\n            <jats:sc>ABEL<\/jats:sc>\n            C\n            <jats:sc>OVER<\/jats:sc>\n            , and W\n            <jats:sc>EIGHTED<\/jats:sc>\n            <jats:italic>d<\/jats:italic>\n            -SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms.\n          <\/jats:p>\n          <jats:p>We also show how to derandomize our algorithms at the cost of a subexponential multiplicative factor in the running time. Our derandomization is based on an efficient construction of a new pseudo-random object that might be of independent interest. Finally, we extend our methods to establish new combinatorial upper bounds and develop enumeration algorithms.<\/jats:p>","DOI":"10.1145\/3284176","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T13:16:43Z","timestamp":1552051003000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Exact Algorithms via Monotone Local Search"],"prefix":"10.1145","volume":"66","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[{"name":"UNSW Sydney 8 Data61, CSIRO, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway 8 Institute of Mathematical Sciences, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798607"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 21st Annual European Symposium on Algorithms (ESA\u201913)","volume":"8125","author":"Bliznets Ivan","year":"2013","unstructured":"Ivan Bliznets , Fedor V. Fomin , Michal Pilipczuk , and Yngve Villanger . 2013 . Largest chordal and interval subgraphs faster than 2<sup>n<\/sup> . In Proceedings of the 21st Annual European Symposium on Algorithms (ESA\u201913) (Lecture Notes in Computer Science) , Vol. 8125 . Springer, 193--204. Ivan Bliznets, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. 2013. Largest chordal and interval subgraphs faster than 2<sup>n<\/sup>. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA\u201913) (Lecture Notes in Computer Science), Vol. 8125. Springer, 193--204."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_9"},{"key":"e_1_2_1_7_1","volume-title":"Van Bang Le, and Jeremy P. Spinrad","author":"Brandst\u00e4dt Andreas","year":"1999","unstructured":"Andreas Brandst\u00e4dt , Van Bang Le, and Jeremy P. Spinrad . 1999 . Graph Classes : A Survey. SIAM. Andreas Brandst\u00e4dt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes: A Survey. SIAM."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_25"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884512"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9904-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_23"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"e_1_2_1_14_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00174-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.11.012"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897551"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1409020.1409030"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9731-6"},{"key":"e_1_2_1_23_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch . 2010 . Exact Exponential Algorithms. Springer . An EATCS Series: Texts in Theoretical Computer Science. Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer. An EATCS Series: Texts in Theoretical Computer Science."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI\u201912)","author":"Gaspers Serge","year":"2012","unstructured":"Serge Gaspers , Eun Jung Kim , Sebastian Ordyniak , Saket Saurabh , and Stefan Szeider . 2012 . Don\u2019t be strict in local search&excl; . In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI\u201912) . AAAI Press. Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, and Stefan Szeider. 2012. Don\u2019t be strict in local search&excl;. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI\u201912). AAAI Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21631"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.041"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_29_1","volume-title":"Congress. Numerant. 19","author":"Peter","year":"1977","unstructured":"Peter L. Hammer and St\u00e9phane F\u00f6ldes. 1977. Split graphs . Congress. Numerant. 19 ( 1977 ), 311--315. Peter L. Hammer and St\u00e9phane F\u00f6ldes. 1977. Split graphs. Congress. Numerant. 19 (1977), 311--315."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Stasys Jukna. 2011. Extremal Combinatorics. Springer.  Stasys Jukna. 2011. Extremal Combinatorics. Springer.","DOI":"10.1007\/978-3-642-17364-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12691-3_22"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915)","author":"Kant\u00e9 Mamadou Moustapha","year":"2015","unstructured":"Mamadou Moustapha Kant\u00e9 , Eun Jung Kim , O.-joung Kwon, and Christophe Paul . 2015 . An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion . In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915) . CoRR 43, 138--150. Retrieved from http:\/\/arxiv.org\/abs\/1504.05905 Mamadou Moustapha Kant\u00e9, Eun Jung Kim, O.-joung Kwon, and Christophe Paul. 2015. An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915). CoRR 43, 138--150. Retrieved from http:\/\/arxiv.org\/abs\/1504.05905"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915)","volume":"45","author":"Kolay Sudeshna","year":"2015","unstructured":"Sudeshna Kolay and Fahad Panolan . 2015 . Parameterized algorithms for deletion to (r,l)-graphs . In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915) (LIPIcs), Vol. 45 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 420--433. Sudeshna Kolay and Fahad Panolan. 2015. Parameterized algorithms for deletion to (r,l)-graphs. In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915) (LIPIcs), Vol. 45. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 420--433."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190621"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","volume":"47","author":"Kumar Mithilesh","year":"2016","unstructured":"Mithilesh Kumar and Daniel Lokshtanov . 2016 . Faster exact and parameterized algorithm for feedback vertex set in tournaments . In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS\u201916) (LIPIcs), Vol. 47 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 49:1--49:13. Mithilesh Kumar and Daniel Lokshtanov. 2016. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS\u201916) (LIPIcs), Vol. 47. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 49:1--49:13."},{"key":"e_1_2_1_38_1","volume-title":"Using CSP to improve deterministic 3-SAT. CoRR abs\/1007.1166","author":"Kutzkov Konstantin","year":"2010","unstructured":"Konstantin Kutzkov and Dominik Scheder . 2010. Using CSP to improve deterministic 3-SAT. CoRR abs\/1007.1166 ( 2010 ). Retrieved from http:\/\/arxiv.org\/abs\/1007.1166. Konstantin Kutzkov and Dominik Scheder. 2010. Using CSP to improve deterministic 3-SAT. CoRR abs\/1007.1166 (2010). Retrieved from http:\/\/arxiv.org\/abs\/1007.1166."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004235"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.004"},{"key":"e_1_2_1_41_1","first-page":"345","article-title":"On maximal transitive subtournaments. Proc. Edinburgh","volume":"17","author":"Moon J. W.","year":"1971","unstructured":"J. W. Moon . 1971 . On maximal transitive subtournaments. Proc. Edinburgh Math. Soc. (2) 17 (1971), 345 -- 349 . J. W. Moon. 1971. On maximal transitive subtournaments. Proc. Edinburgh Math. Soc. (2) 17 (1971), 345--349.","journal-title":"Math. Soc. (2)"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993670"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796315"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785293_17"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812770998_0010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796524"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.05.003"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9661-3"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634202"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_31"},{"key":"e_1_2_1_52_1","first-page":"1052","article-title":"Complexity and completeness of finding another solution and its application to puzzles. IEICE","volume":"5","author":"Yato Takayuki","year":"2003","unstructured":"Takayuki Yato and Takahiro Seta . 2003 . Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E86-A , 5 (2003), 1052 -- 1060 . Takayuki Yato and Takahiro Seta. 2003. Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E86-A, 5 (2003), 1052--1060.","journal-title":"Trans. Fund. Electron. Commun. Comput. Sci. E86-A"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:01Z","timestamp":1750208881000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,8]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3284176"],"URL":"https:\/\/doi.org\/10.1145\/3284176","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,8]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}