{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:35Z","timestamp":1740109595074,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T00:00:00Z","timestamp":1673654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T00:00:00Z","timestamp":1673654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001412","name":"council of scientific and industrial research, india","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001412","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005276","name":"national board for higher mathematics","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005276","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013233","name":"sponsored research and industrial consultancy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013233","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00454-022-00472-y","type":"journal-article","created":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T20:02:36Z","timestamp":1673726556000},"page":"307-322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Maximum Cut on Interval Graphs"],"prefix":"10.1007","volume":"70","author":[{"given":"Ranendu","family":"Adhikary","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3579-1941","authenticated-orcid":false,"given":"Kaustav","family":"Bose","sequence":"additional","affiliation":[]},{"given":"Satwik","family":"Mukherjee","sequence":"additional","affiliation":[]},{"given":"Bodhayan","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,14]]},"reference":[{"key":"472_CR1","unstructured":"Adhikary, R., Bose, K., Mukherjee, S., Roy, B.: Complexity of maximum cut on interval graphs (2020). arXiv:2006.00061"},{"key":"472_CR2","unstructured":"Adhikary, R., Bose, K., Mukherjee, S., Roy, B.: Complexity of maximum cut on interval graphs. In: 37th International Symposium on Computational Geometry. Leibniz International Proceedings in Informatics, vol. 189, #\u00a07. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2021)"},{"issue":"17","key":"472_CR3","doi-asserted-by":"publisher","first-page":"2377","DOI":"10.1016\/j.dam.2007.07.005","volume":"155","author":"K Asdre","year":"2007","unstructured":"Asdre, K., Ioannidou, K., Nikolopoulos, S.D.: The harmonious coloring problem is NP-complete for interval and permutation graphs. Discrete Appl. Math. 155(17), 2377\u20132382 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"472_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F Barahona","year":"1983","unstructured":"Barahona, F.: The max-cut problem on graphs not contractible to $$K_5$$. Oper. Res. Lett. 2(3), 107\u2013111 (1983)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"472_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"key":"472_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: 26th International Colloquium on Automata, Languages and Programming (Prague 1999). Lecture Notes in Computer Science, vol. 1644, pp. 200\u2013209. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"issue":"3","key":"472_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(89)90221-4","volume":"31","author":"HL Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: Achromatic number is NP-complete for cographs and interval graphs. Inform. Process. Lett. 31(3), 135\u2013138 (1989)","journal-title":"Inform. Process. Lett."},{"key":"472_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., de Figueiredo, C.M.H., Gutierrez, M., Kloks, T., Niedermeier, R.: Simple max-cut for split-indifference graphs and graphs with few $${P_4}$$\u2019s. In: 3rd International Workshop on Experimental and Efficient Algorithms (Angra dos Reis 2004). Lecture Notes in Computer Science, vol. 3059, pp. 87\u201399. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24838-5_7"},{"issue":"1","key":"472_CR9","first-page":"14","volume":"7","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of the maximum cut problem. Nordic J. Comput. 7(1), 14\u201331 (2000)","journal-title":"Nordic J. Comput."},{"key":"472_CR10","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kloks, T., Niedermeier, R.: Simple MAX-CUT for unit interval graphs and graphs with few\u00a0$$P_4$$s. In: 6th Twente Workshop on Graphs and Combinatorial Optimization (Enschede 1999). Electronic Notes in Discrete Mathematics, vol. 3, pp. 19\u201326. Elsevier, Amsterdam (1999)","DOI":"10.1016\/S1571-0653(05)80014-9"},{"key":"472_CR11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.ipl.2017.01.007","volume":"121","author":"A Boyac\u0131","year":"2017","unstructured":"Boyac\u0131, A., Ekim, T., Shalom, M.: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Inform. Process. Lett. 121, 29\u201333 (2017)","journal-title":"Inform. Process. Lett."},{"key":"472_CR12","unstructured":"Chakraborty, D., Das, S., Foucaud, F., Gahlawat, H., Lajou, D., Roy,\u00a0B.: Algorithms and complexity for geodetic sets on planar and chordal graphs. In: 31st International Symposium on Algorithms and Computation. Leibniz International Proceedings in Informatics, vol. 181, #\u00a07. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2020)"},{"key":"472_CR13","doi-asserted-by":"crossref","unstructured":"Chang, K.C., Du, D.H.-Ch.: Efficient algorithms for layer assignment problem. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(1), 67\u201378 (1987)","DOI":"10.1109\/TCAD.1987.1270247"},{"issue":"6","key":"472_CR14","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M-Sh Chang","year":"1998","unstructured":"Chang, M.-Sh.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"key":"472_CR15","unstructured":"Cohen, J.E., Stephens, D.W.: Food Webs and Niche Space. Monographs in Population Biology, vol. 11. Princeton University Press, Princeton (1978)"},{"key":"472_CR16","doi-asserted-by":"crossref","unstructured":"Cohen, J., Fomin, F., Heggernes, P., Kratsch, D., Kucherov, G.: Optimal linear arrangement of interval graphs. In: Mathematical Foundations of Computer Science (Star\u00e1 Lesn\u00e1 2006). Lecture Notes in Computer Science, vol. 4162, pp. 267\u2013279. Springer, Berlin (2006)","DOI":"10.1007\/11821069_24"},{"issue":"3","key":"472_CR17","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1007\/s00453-014-9870-z","volume":"72","author":"R Crowston","year":"2015","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-cut parameterized above the Edwards\u2013Erd\u0151s bound. Algorithmica 72(3), 734\u2013757 (2015)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"472_CR18","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.tcs.2007.02.013","volume":"377","author":"J D\u00edaz","year":"2007","unstructured":"D\u00edaz, J., Kami\u0144ski, M.: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theoret. Comput. Sci. 377(1\u20133), 271\u2013276 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"472_CR19","unstructured":"de Figueiredo, C.M.H., de Melo, A.A., Oliveira, F.S., Silva, A.: Maximum cut on interval graphs of interval count four is NP-complete. In: 46th International Symposium on Mathematical Foundations of Computer Science (Tallinn 2021). Leibniz International Proceedings in Informatics, vol. 202, #\u00a038. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2021)"},{"issue":"5","key":"472_CR20","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"472_CR21","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1007\/s00453-016-0184-1","volume":"78","author":"F Foucaud","year":"2017","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs II. Algorithms and complexity. Algorithmica 78(3), 914\u2013944 (2017)","journal-title":"Algorithmica"},{"key":"472_CR22","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1990)"},{"issue":"6","key":"472_CR23","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. J. Assoc. Comput. Mach. 42(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"472_CR24","doi-asserted-by":"crossref","unstructured":"Golumbic, M.Ch.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. Elsevier, Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"2\u20133","key":"472_CR25","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(99)00056-6","volume":"92","author":"V Guruswami","year":"1999","unstructured":"Guruswami, V.: Maximum cut on line and total graphs. Discrete Appl. Math. 92(2\u20133), 217\u2013221 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"472_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"472_CR27","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. J. Assoc. Comput. Mach. 48(4), 798\u2013859 (2001)","journal-title":"J. Assoc. Comput. Mach."},{"key":"472_CR28","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Meister, D., Papadopoulos, Ch.: A new representation of proper interval graphs with an application to clique-width. In: DIMAP Workshop on Algorithmic Graph Theory (Coventry 2009). Electronic Notes in Discrete Mathematics, vol. 32, pp. 27\u201334. Elsevier, Amsterdam (2009)","DOI":"10.1016\/j.endm.2009.02.005"},{"issue":"4","key":"472_CR29","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H Imai","year":"1983","unstructured":"Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4(4), 310\u2013323 (1983)","journal-title":"J. Algorithms"},{"issue":"3","key":"472_CR30","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"DS Johnson","year":"1985","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 6(3), 434\u2013451 (1985)","journal-title":"J. Algorithms"},{"issue":"3","key":"472_CR31","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0303-2647(82)90010-7","volume":"15","author":"JR Jungck","year":"1982","unstructured":"Jungck, J.R., Dick, G., Gleason Dick, A.: Computer-assisted sequencing, interval graphs, and molecular evolution. Biosystems 15(3), 259\u2013273 (1982)","journal-title":"Biosystems"},{"key":"472_CR32","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2012.02.036","volume":"438","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M.: MAX-CUT and containment relations in graphs. Theoret. Comput. Sci. 438, 89\u201395 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"472_CR33","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Yorktown Heights 1972), pp. 85\u2013103. Plenum, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"472_CR34","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding Hamiltonian circuits in interval graphs. Inform. Process. Lett. 20(4), 201\u2013206 (1985)","journal-title":"Inform. Process. Lett."},{"key":"472_CR35","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique $$2$$-prover $$1$$-round games. In: 34th Annual ACM Symposium on Theory of Computing (Montr\u00e9al 2002), pp. 767\u2013775. ACM, New York (2002)","DOI":"10.1145\/509907.510017"},{"key":"472_CR36","doi-asserted-by":"crossref","unstructured":"Kobayashi, Ya., Kobayashi, Yu., Miyazaki, Sh., Tamaki, S.: An improved fixed-parameter algorithm for max-cut parameterized by crossing number. In: 30th International Workshop on Combinatorial Algorithms (Pisa 2019). Lecture Notes in Computer Science, vol. 11638, pp. 327\u2013338. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-25005-8_27"},{"key":"472_CR37","unstructured":"Kratochv\u00edl, J., Masa\u0159\u00edk, T., Novotn\u00e1, J.: $${{\\cal{U}}}$$-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. In: 45th International Symposium on Mathematical Foundations of Computer Science (Prague 2020). Leibniz International Proceedings in Informatics, vol. 170, #\u00a057. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2020)"},{"issue":"2","key":"472_CR38","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","volume":"61","author":"ChL Lu","year":"1997","unstructured":"Lu, Ch.L., Tang, Ch.Y.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inform. Process. Lett. 61(2), 107\u2013111 (1997)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"472_CR39","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/s00224-018-09909-5","volume":"64","author":"J Madathil","year":"2020","unstructured":"Madathil, J., Saurabh, S., Zehavi, M.: Fixed-parameter tractable algorithm and polynomial kernel for max-cut above spanning tree. Theory Comput. Syst. 64(1), 62\u2013100 (2020)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"472_CR40","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"472_CR41","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0166-218X(92)90116-R","volume":"39","author":"MV Marathe","year":"1992","unstructured":"Marathe, M.V., Ravi, R., Pandu Rangan, C.: Generalized vertex covering in interval graphs. Discrete Appl. Math. 39(1), 87\u201393 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"472_CR42","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D Marx","year":"2005","unstructured":"Marx, D.: A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett. 33(4), 382\u2013384 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"472_CR43","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"ChH Papadimitriou","year":"1991","unstructured":"Papadimitriou, Ch.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"472_CR44","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2007.05.014","volume":"104","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S.: Improved fixed parameter tractable algorithms for two \u201cedge\u2019\u2019 problems: MAXCUT and MAXDAG. Inform. Process. Lett. 104(2), 65\u201372 (2007)","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"472_CR45","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"472_CR46","unstructured":"Utkarsh, J., Rahul, S., Thoppil, J.J.: Algorithms for max cut on unit interval and laminar interval graphs. In: Computational Geometry: Young Researchers Forum 2021, pp. 37\u201339. https:\/\/cse.buffalo.edu\/socg21\/files\/YRF-Booklet.pdf"},{"issue":"3","key":"472_CR47","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/bioinformatics\/10.3.309","volume":"10","author":"P Zhang","year":"1994","unstructured":"Zhang, P., Schon, E.A., Fischer, S.G., Cayanis, E., Weiss, J., Kistler, S., Bourne, Ph.E.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Bioinformatics 10(3), 309\u2013317 (1994)","journal-title":"Bioinformatics"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00472-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00472-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00472-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T19:02:10Z","timestamp":1691866930000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00472-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,14]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["472"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00472-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,1,14]]},"assertion":[{"value":"30 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}