{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:16:05Z","timestamp":1787505365979,"version":"build-2736575974"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) grant \u201cPARAMTIGHT: Parameterized complexity and the search for tight complexity results,\u201d","award":["280152"],"award-info":[{"award-number":["280152"]}]},{"DOI":"10.13039\/501100003549","name":"OTKA","doi-asserted-by":"crossref","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","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":[[2016,2,3]]},"abstract":"<jats:p>\n                    For a finite set \u0393 of Boolean relations, M\n                    <jats:sc>ax<\/jats:sc>\n                    O\n                    <jats:sc>nes<\/jats:sc>\n                    SAT(\u0393) and E\n                    <jats:sc>xact<\/jats:sc>\n                    O\n                    <jats:sc>nes<\/jats:sc>\n                    SAT(\u0393) are generalized satisfiability problems where every constraint relation is from \u0393, and the task is to find a satisfying assignment with at least\/exactly\n                    <jats:italic>k<\/jats:italic>\n                    variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For M\n                    <jats:sc>ax<\/jats:sc>\n                    O\n                    <jats:sc>nes<\/jats:sc>\n                    SAT(\u0393), we give a classification into five different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed\n                    <jats:italic>k<\/jats:italic>\n                    , and NP-hard already for\n                    <jats:italic>k<\/jats:italic>\n                    = 1. For E\n                    <jats:sc>xact<\/jats:sc>\n                    O\n                    <jats:sc>nes<\/jats:sc>\n                    SAT(\u0393), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets \u0393 for which E\n                    <jats:sc>xact<\/jats:sc>\n                    O\n                    <jats:sc>nes<\/jats:sc>\n                    SAT(\u0393) admits a polynomial kernel.\n                  <\/jats:p>","DOI":"10.1145\/2858787","type":"journal-article","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T11:29:01Z","timestamp":1454498941000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems"],"prefix":"10.1145","volume":"8","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[{"name":"Max-Planck-Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Control, Hungarian Academy of Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Max-Planck-Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652168"},{"key":"e_1_2_1_5_1","volume-title":"Tractable conservative constraint satisfaction problems","author":"Bulatov Andrei A.","unstructured":"Andrei A. Bulatov . 2003. Tractable conservative constraint satisfaction problems . In LICS. IEEE , 321. Andrei A. Bulatov. 2003. Tractable conservative constraint satisfaction problems. In LICS. IEEE, 321."},{"key":"e_1_2_1_6_1","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications","volume":"7","author":"Creignou N.","unstructured":"N. Creignou , S. Khanna , and M. Sudan . 2001 . Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications , Vol. 7 . N. Creignou, S. Khanna, and M. Sudan. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, Vol. 7."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.02.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87531-4_10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00146-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York.   R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_14_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Danny Hermelin Stefan Kratsch Karolina Soltys Magnus Wahlstr\u00f6m and Xi Wu. 2013. A completeness theory for polynomial (turing) kernelization. In IPEC. 202--215.  Danny Hermelin Stefan Kratsch Karolina Soltys Magnus Wahlstr\u00f6m and Xi Wu. 2013. A completeness theory for polynomial (turing) kernelization. In IPEC. 202--215.","DOI":"10.1007\/978-3-319-03898-8_18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_17_1","volume-title":"MFCS (LNCS)","author":"Kratsch Stefan","unstructured":"Stefan Kratsch , D\u00e1niel Marx , and Magnus Wahlstr\u00f6m . 2010. Parameterized complexity and kernelizability of max ones and exact ones problems . In MFCS (LNCS) , Vol. 6281 . Springer Berlin , 489--500. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-15155-2_43 10.1007\/978-3-642-15155-2_43 Stefan Kratsch, D\u00e1niel Marx, and Magnus Wahlstr\u00f6m. 2010. Parameterized complexity and kernelizability of max ones and exact ones problems. In MFCS (LNCS), Vol. 6281. Springer Berlin, 489--500. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-15155-2_43"},{"key":"e_1_2_1_18_1","volume-title":"ICALP (1)(LNCS)","author":"Kratsch Stefan","unstructured":"Stefan Kratsch and Magnus Wahlstr\u00f6m . 2010. Preprocessing of min ones problems: A dichotomy . In ICALP (1)(LNCS) , Vol. 6198 . Springer Berlin , 653--665. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2_55 10.1007\/978-3-642-14165-2_55 Stefan Kratsch and Magnus Wahlstr\u00f6m. 2010. Preprocessing of min ones problems: A dichotomy. In ICALP (1)(LNCS), Vol. 6198. Springer Berlin, 653--665. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-14165-2_55"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2009.10"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2858787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:48:43Z","timestamp":1750211323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2858787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2858787"],"URL":"https:\/\/doi.org\/10.1145\/2858787","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,3]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}