{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:31:38Z","timestamp":1767339098095,"version":"3.41.0"},"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-03T16:29:01Z","timestamp":1454516941000},"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":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Control, Hungarian Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Max-Planck-Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"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"},{"volume-title":"Tractable conservative constraint satisfaction problems","author":"Bulatov Andrei A.","key":"e_1_2_1_5_1","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"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_14_1","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"},{"volume-title":"MFCS (LNCS)","author":"Kratsch Stefan","key":"e_1_2_1_17_1","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"},{"volume-title":"ICALP (1)(LNCS)","author":"Kratsch Stefan","key":"e_1_2_1_18_1","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-18T05:48:43Z","timestamp":1750225723000},"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":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"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"}}]}}