{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:38Z","timestamp":1750220618635,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["P26200 and P26696"],"award-info":[{"award-number":["P26200 and P26696"]}]},{"name":"FWF","award":["P31336","32441"],"award-info":[{"award-number":["P31336","32441"]}]},{"name":"DFG","award":["NI 369\/12"],"award-info":[{"award-number":["NI 369\/12"]}]},{"DOI":"10.13039\/501100001821","name":"WWTF","doi-asserted-by":"crossref","award":["ICT19-065"],"award-info":[{"award-number":["ICT19-065"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Impagliazzo et\u00a0al.\u00a0proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to\n            <jats:italic>k<\/jats:italic>\n            -CNF-\n            <jats:sc>Sat<\/jats:sc>\n            modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this article, we extend the framework of Impagliazzo et al. and identify a larger set of problems that are equivalent to\n            <jats:italic>k<\/jats:italic>\n            -CNF-\n            <jats:sc>Sat<\/jats:sc>\n            modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second-order logic whose expressions have a linear\n            <jats:italic>measure<\/jats:italic>\n            in terms of a complexity parameter, which is usually the universe size of the problem.\n          <\/jats:p>\n          <jats:p>\n            This research direction can be traced back to Fagin\u2019s celebrated theorem stating that NP\u00a0coincides with the class of problems expressible in existential second-order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential\n            <jats:italic>monadic<\/jats:italic>\n            second-order logic. The proposed class Linear Monadic NP\u00a0is then the restriction of Monadic NP\u00a0to problems whose expressions have linear measure in the complexity parameter.\n          <\/jats:p>\n          <jats:p>\n            We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that\n            <jats:sc>Feedback Vertex Set<\/jats:sc>\n            is inexpressible in existential monadic second-order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between\n            <jats:sc>Feedback Vertex Set<\/jats:sc>\n            (and variants of it) and\n            <jats:sc>3-CNF-Sat<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/3417759","type":"journal-article","created":{"date-parts":[[2020,10,1]],"date-time":"2020-10-01T04:07:32Z","timestamp":1601525252000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Existential MSO and Its Relation to ETH"],"prefix":"10.1145","volume":"12","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald de","family":"Haan","sequence":"additional","affiliation":[{"name":"Institute for Logic, Language and Computation, University of Amsterdam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[{"name":"School of Computing, DePaul University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,30]]},"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.2307\/2274958"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1691"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00015-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_8_1","volume-title":"Math. Proc. Cambr. Philos. Soc. 37","author":"Brooks Rowland L.","year":"1941","unstructured":"Rowland L. Brooks . 1941. On colouring the nodes of a network . Math. Proc. Cambr. Philos. Soc. 37 , 2 (4 1941 ), 194--197. DOI:https:\/\/doi.org\/10.1017\/S030500410002168X 10.1017\/S030500410002168X Rowland L. Brooks. 1941. On colouring the nodes of a network. Math. Proc. Cambr. Philos. Soc. 37, 2 (4 1941), 194--197. DOI:https:\/\/doi.org\/10.1017\/S030500410002168X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.48"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1103348.1709478"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765236.1765240"},{"volume-title":"Graph Structure and Monadic Second-order Logic: A Language-theoretic Approach","author":"Courcelle Bruno","key":"e_1_2_1_15_1","unstructured":"Bruno Courcelle and Joost Engelfriet . 2012. Graph Structure and Monadic Second-order Logic: A Language-theoretic Approach . Cambridge University Press , Cambridge, UK . Bruno Courcelle and Joost Engelfriet. 2012. Graph Structure and Monadic Second-order Logic: A Language-theoretic Approach. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90353-J"},{"key":"e_1_2_1_17_1","volume-title":"Error-correcting codes on the towers of Hanoi graphs. Disc. Math. 208--209","author":"Cull Paul","year":"1999","unstructured":"Paul Cull and Ingrid Nelson . 1999. Error-correcting codes on the towers of Hanoi graphs. Disc. Math. 208--209 ( 1999 ), 157--175. Paul Cull and Ingrid Nelson. 1999. Error-correcting codes on the towers of Hanoi graphs. Disc. Math. 208--209 (1999), 157--175."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884547"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_19_1","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.1016\/S0304-3975(01)00174-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14186-7_27"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer Verlag New York.  R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_24_1","first-page":"43","article-title":"Generalized first-order spectra, and polynomial time recognizable sets","volume":"7","author":"Fagin R.","year":"1974","unstructured":"R. Fagin . 1974 . Generalized first-order spectra, and polynomial time recognizable sets . SIAM-AMS Proc. 7 (1974), 43 -- 73 . R. Fagin. 1974. Generalized first-order spectra, and polynomial time recognizable sets. SIAM-AMS Proc. 7 (1974), 43--73.","journal-title":"SIAM-AMS Proc."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Logic and Computational Complexity Workshop (LCC\u201994)","volume":"960","author":"Fagin Ronald","year":"1994","unstructured":"Ronald Fagin . 1994 . Comparing the power of monadic NP games . In Proceedings of the International Logic and Computational Complexity Workshop (LCC\u201994) . Selected Papers. (Lecture Notes in Computer Science), Daniel Leivant (Ed.) , Vol. 960 . Springer, 414--425. Ronald Fagin. 1994. Comparing the power of monadic NP games. In Proceedings of the International Logic and Computational Complexity Workshop (LCC\u201994). Selected Papers. (Lecture Notes in Computer Science), Daniel Leivant (Ed.), Vol. 960. Springer, 414--425."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1100"},{"key":"e_1_2_1_28_1","first-page":"71","article-title":"Parameterized complexity and subexponential time","volume":"84","author":"Flum J\u00f6rg","year":"2004","unstructured":"J\u00f6rg Flum and Martin Grohe . 2004 . Parameterized complexity and subexponential time . Bull. Euro. Assoc. Theor. Comput. Sci. 84 (2004), 71 -- 100 . J\u00f6rg Flum and Martin Grohe. 2004. Parameterized complexity and subexponential time. Bull. Euro. Assoc. Theor. Comput. Sci. 84 (2004), 71--100.","journal-title":"Bull. Euro. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_29_1","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science . An EATCS Series , Vol. XIV . Springer Verlag , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Vol. XIV. Springer Verlag, Berlin."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1409020.1409030"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"F. V. Fomin and D. Kratsch. 2010. Exact Exponential Algorithms. Springer Verlag.  F. V. Fomin and D. Kratsch. 2010. Exact Exponential Algorithms. Springer Verlag.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_2_1_32_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David R . Johnson . 1979 . Computers and Intractability. W. H. Freeman and Company , New York, San Francisco. Michael R. Garey and David R. Johnson. 1979. Computers and Intractability. W. H. Freeman and Company, New York, San Francisco."},{"key":"e_1_2_1_33_1","article-title":"Distance domination and distance irredundance in graphs","volume":"14","author":"Hansberg Adriana","year":"2007","unstructured":"Adriana Hansberg , Dirk Meierling , and Lutz Volkmann . 2007 . Distance domination and distance irredundance in graphs . Electr. J. Comb. 14 , 1 (2007). Adriana Hansberg, Dirk Meierling, and Lutz Volkmann. 2007. Distance domination and distance irredundance in graphs. Electr. J. Comb. 14, 1 (2007).","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer Verlag.  Neil Immerman. 1999. Descriptive Complexity. Springer Verlag.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_31"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","author":"Johnson D.","key":"e_1_2_1_37_1","unstructured":"D. Johnson and M. Szegedy . 1999. What are the least tractable instances of max. independent set? In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999) . 927--928. D. Johnson and M. Szegedy. 1999. What are the least tractable instances of max. independent set? In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999). 927--928."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.029"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 12th International Workshop on Computer Science Logic. (Lecture Notes in Computer Science)","volume":"1584","author":"Kreidler Martin","year":"1998","unstructured":"Martin Kreidler and Detlef Seese . 1998 . Monadic NP and graph minors . In Proceedings of the 12th International Workshop on Computer Science Logic. (Lecture Notes in Computer Science) , Vol. 1584 . Springer, 126--141. Martin Kreidler and Detlef Seese. 1998. Monadic NP and graph minors. In Proceedings of the 12th International Workshop on Computer Science Logic. (Lecture Notes in Computer Science), Vol. 1584. Springer, 126--141."},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_2_1_40_1","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer Verlag . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer Verlag."},{"key":"e_1_2_1_41_1","unstructured":"Daniel Lokshtanov. 2015. Personal communication.  Daniel Lokshtanov. 2015. Personal communication."},{"key":"e_1_2_1_42_1","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2011 . Lower bounds based on the exponential time hypothesis . Bull. Euro. Assoc. Theor. Comput. Sci. 105 (2011), 41 -- 72 . Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. Euro. Assoc. Theor. Comput. Sci. 105 (2011), 41--72.","journal-title":"Bull. Euro. Assoc. Theor. Comput. Sci."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/647848.736917"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31770-5_22"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00030-5"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_73"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3417759"],"URL":"https:\/\/doi.org\/10.1145\/3417759","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}