{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:30:57Z","timestamp":1787319057994,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Monotone monadic strict NP (MMSNP) is a class of computational problems that is closely related to the class of constraint satisfaction problems for constraint languages over finite domains. It is known that one of those classes has a complexity dichotomy if and only if the other class has. Whereas the dichotomy conjecture has been verified for several subclasses of constraint satisfaction problems, little is known about the the computational complexity for subclasses of MMSNP. In this paper we completely classify the complexity of MMSNP for the case where the obstructions are monochromatic and where loops in the input are forbidden. That is, we determine the computational complexity of natural partition problems of the following type. For fixed sets of finite structures ${\\cal S}_1, \\dots, {\\cal S}_k$, decide whether a given loopless structure can be vertex-partitioned into k parts such that for each $i \\leq k$ none of the structures in ${\\cal S}_i$ is homomorphic to the ith part.<\/jats:p>","DOI":"10.1137\/090778493","type":"journal-article","created":{"date-parts":[[2012,3,29]],"date-time":"2012-03-29T18:55:38Z","timestamp":1333047338000},"page":"404-414","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of MMSNP"],"prefix":"10.1137","volume":"26","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1s","family":"Feder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,3,29]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)84217-3"},{"key":"R2","unstructured":"M. Bodirsky and V. Dalmau,\n                      Datalog and constraint satisfaction with infinite templates\n                      , preprint, 2008, available online at arXiv:0809.2386."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and J. K\u00e1ra,\n                      The complexity of temporal constraint satisfaction problems\n                      , J. ACM, 57 (2009), 9.","DOI":"10.1145\/1667053.1667058"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Bodirsky and M. Pinsker,\n                      Schaefer's theorem for graphs\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 655\u2013664.","DOI":"10.1145\/1993636.1993724"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan,\n                      Complexity Classifications of Boolean Constraint Satisfaction Problems\n                      , SIAM Monogr. Discrete Math. Appl. 7, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"R9","unstructured":"G. Kun,\n                      Constraints, MMSNP, and Expander Relational Structures\n                      , preprint available at arXiv:0706.1701, 2007."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"G. Kun and J. Ne\u0161et\u0159il,\n                      NP by means of lifts and shadows\n                      , in Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, 2007, pp. 171\u2013181.","DOI":"10.1007\/978-3-540-74456-6_17"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/050634840"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978, pp. 216\u2013226.","DOI":"10.1145\/800133.804350"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090778493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:44:48Z","timestamp":1787316288000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090778493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/090778493"],"URL":"https:\/\/doi.org\/10.1137\/090778493","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}