{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:15:47Z","timestamp":1778717747832,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:00:00Z","timestamp":1778630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:00:00Z","timestamp":1778630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Division of Computing and Communication Foundations, United States"},{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00224-026-10276-9","type":"journal-article","created":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T11:30:46Z","timestamp":1778671846000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Algorithmic Analysis of MAXNAESAT Variants"],"prefix":"10.1007","volume":"70","author":[{"given":"Sangram K.","family":"Jena","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,13]]},"reference":[{"issue":"1\u20132","key":"10276_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some apx-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"10276_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. In: International Colloquium on Automata, Languages, and Programming, pages 200\u2013209 (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"issue":"1","key":"10276_CR3","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/23M1591578","volume":"39","author":"J Brakensiek","year":"2025","unstructured":"Brakensiek, J., Huang, N., Potechin, A., Zwick, U.: On the mysteries of max nae-sat. SIAM J. Discret. Math. 39(1), 267\u2013313 (2025)","journal-title":"SIAM J. Discret. Math."},{"key":"10276_CR4","unstructured":"Clarke, E.\u00a0M., Grumberg, O., Peled, D.\u00a0A.: Model checking, (2000)"},{"key":"10276_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S.\u00a0A.: The complexity of theorem-proving procedures. In: ACM Symposium on Theory of Computing (1971)","DOI":"10.1145\/800157.805047"},{"issue":"4","key":"10276_CR6","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1007\/s00453-014-9883-7","volume":"72","author":"K Edwards","year":"2015","unstructured":"Edwards, K., McDermid, E.: A general reduction theorem with applications to pathwidth and the complexity of max 2-csp. Algorithmica 72(4), 940\u2013968 (2015)","journal-title":"Algorithmica"},{"key":"10276_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F.\u00a0V., Kratsch, D.: Exact Exponential Algorithms. Texts Theoretical Computer Science. An EATCS Series. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"10276_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco (1979)"},{"issue":"4","key":"10276_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3111499","volume":"13","author":"S Gaspers","year":"2017","unstructured":"Gaspers, S., Sorkin, G.B.: Separate, measure and conquer: faster polynomial-space algorithms for max 2-csp and counting dominating sets. ACM Transactions on Algorithms (TALG) 13(4), 1\u201336 (2017)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"6","key":"10276_CR10","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"10276_CR11","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM (JACM) 48(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"10276_CR12","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"10276_CR13","doi-asserted-by":"crossref","unstructured":"Jena, S.\u00a0K., Subramani, K.: Computational and approximation complexities of minnaesat variants. Discrete Mathematics, Algorithms and Applications (2025)","DOI":"10.1142\/S179383092550154X"},{"key":"10276_CR14","doi-asserted-by":"crossref","unstructured":"Jena, S.\u00a0K., Subramani, K.: From maxcut to maxnaesat: Elegant proofs and algorithmic advances. In: International Workshop on Frontiers in Algorithmics, pages 103\u2013117. Springer (2025)","DOI":"10.1007\/978-981-96-8312-3_8"},{"key":"10276_CR15","doi-asserted-by":"crossref","unstructured":"Kann, V., Lagergren, J., Panconesi, A.: Approximability of Maximum Splitting of k-sets and some other APX-complete Problems. Citeseer, (1995)","DOI":"10.1016\/0020-0190(96)00046-4"},{"issue":"1","key":"10276_CR16","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"10276_CR17","unstructured":"Lee, A., Xu, B.: Classifying approximation algorithms: understanding the apx complexity class (2021). arXiv preprint arXiv:2111.01551"},{"key":"10276_CR18","unstructured":"Anbulagan, L. L., Meyer, T., Ghose, A.\u00a0K.: Modeling and Solving Semiring Constraint Satisfaction Problems by Transformation to Weighted Semiring Max-SAT. In: Orgun, M.\u00a0A., Thornton, J. (eds.), AI 2007: Advances in Artificial Intelligence, 20th Australian Joint Conference on Artificial Intelligence, Gold Coast, Australia, December 2-6, 2007, Proceedings, volume 4830 of Lecture Notes in Computer Science, pages 202\u2013212. Springer, (2007)"},{"key":"10276_CR19","doi-asserted-by":"crossref","unstructured":"Li, W., Xu, C., Wang, J., Yang, Y.: An improved branching algorithm for (n, 3)-maxsat based on refined observations. In: International Conference on Combinatorial Optimization and Applications, pages 94\u2013108 (2017)","DOI":"10.1007\/978-3-319-71147-8_7"},{"key":"10276_CR20","doi-asserted-by":"crossref","unstructured":"Misra, N., Ordyniak, S., Raman, V., Szeider, S.: Upper and lower bounds for weak backdoor set detection. In: J\u00e4rvisalo, M., Gelder, A.\u00a0V. (eds.), Theory and Applications of Satisfiability Testing - SAT 2013 - 16th International Conference, Helsinki, Finland, July 8-12, 2013. Proceedings, volume 7962 of Lecture Notes in Computer Science, pages 394\u2013402. Springer (2013)","DOI":"10.1007\/978-3-642-39071-5_29"},{"key":"10276_CR21","volume-title":"Papadimitriou","author":"H Christos","year":"1994","unstructured":"Christos, H.: Papadimitriou. Addison-Wesley, Computational complexity (1994)"},{"issue":"3","key":"10276_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"10276_CR23","doi-asserted-by":"crossref","unstructured":"Porschen, S., Randerath, B., Speckenmeyer, E.: Linear Time Algorithms for Some Not-All-Equal Satisfiability Problems. In: SAT, pages 172\u2013187 (2003)","DOI":"10.1007\/978-3-540-24605-3_14"},{"issue":"1","key":"10276_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified np-complete MAXSAT problem. Inf. Process. Lett. 65(1), 1\u20136 (1998)","journal-title":"Inf. Process. Lett."},{"key":"10276_CR25","doi-asserted-by":"crossref","unstructured":"St\u00e5lmarck, G., S\u00e4flund, M.: Modeling and verifying systems and software in propositional logic. In: Safety of Computer Control Systems 1990 (Safecomp\u201990), pages 31\u201336. Elsevier (1990)","DOI":"10.1016\/B978-0-08-040953-5.50011-8"},{"issue":"3","key":"10276_CR26","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1080\/00207161003631893","volume":"88","author":"K Subramani","year":"2011","unstructured":"Subramani, K., Gu, X.: Absorbing random walks and the NAE2SAT problem. Int. J. Comput. Math. 88(3), 452\u2013467 (2011)","journal-title":"Int. J. Comput. Math."},{"issue":"2\u20133","key":"10276_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"10276_CR28","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2016.05.040","volume":"657","author":"A Xian","year":"2017","unstructured":"Xian, A., Zhu, K., Zhu, D., Lianrong, P., Liu, H.: Approximating Max NAE-k-SAT by anonymous local search. Theoret. Comput. Sci. 657, 54\u201363 (2017)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"10276_CR29","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.dam.2002.07.001","volume":"142","author":"J Zhang","year":"2004","unstructured":"Zhang, J., Ye, Y., Han, Q.: Improved approximations for max set splitting and max NAE SAT. Discret. Appl. Math. 142(1\u20133), 133\u2013149 (2004)","journal-title":"Discret. Appl. Math."},{"key":"10276_CR30","first-page":"201","volume":"98","author":"U Zwick","year":"1998","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In SODA 98, 201\u2013210 (1998)","journal-title":"In SODA"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10276-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10276-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10276-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T00:03:18Z","timestamp":1778716998000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10276-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,13]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10276"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10276-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,13]]},"assertion":[{"value":"29 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"34"}}