{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:43Z","timestamp":1740109303662,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:00:00Z","timestamp":1630540800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:00:00Z","timestamp":1630540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007397","name":"Univerzita Karlova v Praze","doi-asserted-by":"publisher","award":["SVV\u20132020\u2013260578"],"award-info":[{"award-number":["SVV\u20132020\u2013260578"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-17314J"],"award-info":[{"award-number":["19-17314J"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs\u2014a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a richer class of graphs. In particular, mixed unit interval graphs may contain a claw as an induced subgraph, as opposed to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs and demonstrate the advantages of this generalized model by providing a subexponential-time algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomial-time algorithm for certain subclasses of mixed unit interval graphs. We point out a substantial mistake in the proof of the polynomiality of the MaxCut problem on unit interval graphs by Boyac\u0131 et al. (Inf Process Lett 121:29\u201333, 2017. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"https:\/\/doi.org\/10.1016\/j.ipl.2017.01.007\">10.1016\/j.ipl.2017.01.007<\/jats:ext-link>). Hence, the time complexity of this problem on unit interval graphs remains open. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs.<\/jats:p>","DOI":"10.1007\/s00453-021-00837-4","type":"journal-article","created":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T22:22:38Z","timestamp":1630707758000},"page":"3649-3680","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["$${\\mathcal {U}}$$-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2620-6133","authenticated-orcid":false,"given":"Jan","family":"Kratochv\u00edl","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7955-4692","authenticated-orcid":false,"given":"Jana","family":"Novotn\u00e1","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,2]]},"reference":[{"unstructured":"Adhikary, R., Bose, K., Mukherjee, S., Roy, B.: Complexity of maximum cut on interval graphs, 2020, accepted to SoCG \u201921\u2019. arXiv:2006.00061","key":"837_CR1"},{"doi-asserted-by":"publisher","unstructured":"Arora, S.: Barak, B., Steurer, D. : Subexponential algorithms for unique games and related problems. J. ACM 62(5), 1\u201325 (2015). https:\/\/doi.org\/10.1145\/2775105","key":"837_CR2","DOI":"10.1145\/2775105"},{"issue":"11","key":"837_CR3","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benzer","year":"1959","unstructured":"Benzer, S.: On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. U.S.A. 45(11), 1607 (1959). https:\/\/doi.org\/10.1073\/pnas.45.11.1607","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"doi-asserted-by":"publisher","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 Ribeiro, C.C., Martins, S.L. (eds.) Experimental and Efficient Algorithms, Third International Workshop, WEA 2004, Angra dos Reis, Brazil, May 25-28, 2004, Proceedings, volume 3059 of Lecture Notes in Computer Science, pp. 87\u201399. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-24838-5_7","key":"837_CR4","DOI":"10.1007\/978-3-540-24838-5_7"},{"key":"837_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/S1571-0653(05)80014-9","volume":"3","author":"HL Bodlaender","year":"1999","unstructured":"Bodlaender, H.L., Kloks, T., Niedermeier, R.: Simple max-cut for unit interval graphs and graphs with few P$${}_{{4}}$$s. Electron. Notes Discrete Math. 3, 19\u201326 (1999). https:\/\/doi.org\/10.1016\/S1571-0653(05)80014-9","journal-title":"Electron. Notes Discrete Math."},{"issue":"3","key":"837_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"key":"837_CR7","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. Inf. Process. Lett. 121, 29\u201333 (2017). https:\/\/doi.org\/10.1016\/j.ipl.2017.01.007","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"837_CR8","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/s10878-015-9963-x","volume":"35","author":"A Boyac\u0131","year":"2018","unstructured":"Boyac\u0131, A., Ekim, T., Shalom, M.: The maximum cardinality cut problem in co-bipartite chain graphs. J. Comb. Optim. 35(1), 250\u2013265 (2018). https:\/\/doi.org\/10.1007\/s10878-015-9963-x","journal-title":"J. Comb. Optim."},{"doi-asserted-by":"crossref","unstructured":"Boyac\u0131, A., Ekim, T., Shalom, M.: On the maximum cardinality cut problem in proper interval graphs and related graph classes (2020). arXiv:2006.03856","key":"837_CR9","DOI":"10.1016\/j.tcs.2021.10.014"},{"doi-asserted-by":"publisher","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, volume 3. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999). https:\/\/doi.org\/10.1137\/1.9780898719796","key":"837_CR10","DOI":"10.1137\/1.9780898719796"},{"issue":"2","key":"837_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"837_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000). https:\/\/doi.org\/10.1016\/S0166-218X(99)00184-5","journal-title":"Discrete Appl. Math."},{"issue":"22","key":"837_CR13","doi-asserted-by":"publisher","first-page":"3357","DOI":"10.1016\/j.disc.2012.07.037","volume":"312","author":"MC Dourado","year":"2012","unstructured":"Dourado, M.C., Le, V.B., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Mixed unit interval graphs. Discrete Math. 312(22), 3357\u20133363 (2012). https:\/\/doi.org\/10.1016\/j.disc.2012.07.037","journal-title":"Discrete Math."},{"doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width minimization is NP-hard. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21\u201323, 2006, pp. 354\u2013362 (2006). https:\/\/doi.org\/10.1145\/1132516.1132568","key":"837_CR14","DOI":"10.1145\/1132516.1132568"},{"issue":"2","key":"837_CR15","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909\u2013939 (2009). https:\/\/doi.org\/10.1137\/070687256","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"837_CR16","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). https:\/\/doi.org\/10.1137\/130910932","journal-title":"SIAM J. Comput."},{"issue":"22","key":"837_CR17","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","volume":"307","author":"F Gardi","year":"2007","unstructured":"Gardi, F.: The Roberts characterization of proper and unit interval graphs. Discrete Math. 307(22), 2906\u20132908 (2007). https:\/\/doi.org\/10.1016\/j.disc.2006.04.043","journal-title":"Discrete Math."},{"key":"837_CR18","first-page":"33","volume":"86","author":"W Goddard","year":"2008","unstructured":"Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Harris, J.M., Rall, D.F.: Braodcast chromatic numbers of graphs. ARS Comb. 86, 33\u201350 (2008)","journal-title":"ARS Comb."},{"key":"837_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/C2013-0-10739-8","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Comput. Sci. Appl. Math. XX  (1980). https:\/\/doi.org\/10.1016\/C2013-0-10739-8","journal-title":"Comput. Sci. Appl. Math. XX"},{"issue":"3","key":"837_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000). https:\/\/doi.org\/10.1142\/S0129054100000260","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"837_CR21","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5(4), 586\u2013595 (1992). https:\/\/doi.org\/10.1137\/0405048","journal-title":"SIAM J. Discrete Math."},{"key":"837_CR22","first-page":"65","volume":"11","author":"G Haj\u00f3s","year":"1957","unstructured":"Haj\u00f3s, G.: \u00dcber eine art von graphen. Internationale Mathematische Nachrichten 11, 65 (1957)","journal-title":"Internationale Mathematische Nachrichten"},{"key":"837_CR23","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.endm.2009.02.005","volume":"32","author":"P Heggernes","year":"2009","unstructured":"Heggernes, P., Meister, D., Papadopoulos, C.: A new representation of proper interval graphs with an application to clique-width. Electron. Notes Discrete Math. 32, 27\u201334 (2009). https:\/\/doi.org\/10.1016\/j.endm.2009.02.005","journal-title":"Electron. Notes Discrete Math."},{"doi-asserted-by":"publisher","unstructured":"Hopkins, S.B., Schramm, T., Trevisan, L.: Subexponential LPs approximate max-cut. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 943\u2013953 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00092","key":"837_CR24","DOI":"10.1109\/FOCS46700.2020.00092"},{"issue":"4","key":"837_CR25","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1002\/jgt.21831","volume":"79","author":"F Joos","year":"2015","unstructured":"Joos, F.: A characterization of mixed unit interval graphs. J. Graph Theory 79(4), 267\u2013281 (2015). https:\/\/doi.org\/10.1002\/jgt.21831","journal-title":"J. Graph Theory"},{"issue":"3","key":"837_CR26","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/S0097539793258143","volume":"25","author":"H Kaplan","year":"1996","unstructured":"Kaplan, H., Shamir, R.: Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput. 25(3), 540\u2013561 (1996). https:\/\/doi.org\/10.1137\/S0097539793258143","journal-title":"SIAM J. Comput."},{"key":"837_CR27","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.ipl.2018.04.012","volume":"137","author":"M Kim","year":"2018","unstructured":"Kim, M., Lidick\u00fd, B., Masa\u0159\u00edk, T., Pfender, F.: Notes on complexity of packing coloring. Inf. Process. Lett. 137, 6\u201310 (2018). https:\/\/doi.org\/10.1016\/j.ipl.2018.04.012","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"publisher","unstructured":"Kratochv\u00edl, J., Masa\u0159\u00edk, T., Novotn\u00e1, J.: U-bubble model for mixed unit interval graphs and its applications: The maxcut problem revisited. In Esparza, J., Kr\u00e1l\u2019, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pp. 53:1\u201353:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.57","key":"837_CR28","DOI":"10.4230\/LIPIcs.MFCS.2020.57"},{"issue":"7\u20138","key":"837_CR29","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1016\/j.dam.2012.09.013","volume":"161","author":"VB Le","year":"2013","unstructured":"Le, V.B., Rautenbach, D.: Integral mixed unit interval graphs. Discrete Appl. Math. 161(7\u20138), 1028\u20131036 (2013). https:\/\/doi.org\/10.1016\/j.dam.2012.09.013","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"837_CR30","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00026-011-0117-2","volume":"15","author":"VV Lozin","year":"2011","unstructured":"Lozin, V.V.: Minimal classes of graphs of unbounded clique-width. Ann. Comb. 15(4), 707\u2013722 (2011). https:\/\/doi.org\/10.1007\/s00026-011-0117-2","journal-title":"Ann. Comb."},{"issue":"4","key":"837_CR31","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"J Mark Keil","year":"1985","unstructured":"Mark Keil, J.: Finding hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90050-X","journal-title":"Inf. Process. Lett."},{"key":"837_CR32","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.dam.2014.12.001","volume":"185","author":"D Meister","year":"2015","unstructured":"Meister, D., Rotics, U.: Clique-width of full bubble model graphs. Discrete Appl. Math. 185, 138\u2013167 (2015). https:\/\/doi.org\/10.1016\/j.dam.2014.12.001","journal-title":"Discrete Appl. Math."},{"unstructured":"Novotn\u00e1, J.: Computational and structural apects of interval graphs and their variants. (2019). https:\/\/dodo.is.cuni.cz\/handle\/20.500.11956\/80360","key":"837_CR33"},{"unstructured":"Karczmarz, A., Nadara, W., Rz\u0105\u017cewski, P., Zych-Pawlewicz, A.: Parameterized Algorithms Retreat of University of Warsaw (2019). Personal communication","key":"837_CR34"},{"issue":"4","key":"837_CR35","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1002\/jgt.21650","volume":"72","author":"D Rautenbach","year":"2013","unstructured":"Rautenbach, D., Szwarcfiter, J.L.: Unit interval graphs of open and closed intervals. J. Graph Theory 72(4), 418\u2013429 (2013). https:\/\/doi.org\/10.1002\/jgt.21650","journal-title":"J. Graph Theory"},{"unstructured":"Roberts, F.S.: Indifference graphs. Proof Techniques in Graph Theory, pp. 139\u2013146 (1969). https:\/\/ci.nii.ac.jp\/naid\/10025491782\/en\/","key":"837_CR36"},{"doi-asserted-by":"crossref","unstructured":"Roberts, F.S.: Some applications of graph theory. Draft (2000)","key":"837_CR37","DOI":"10.1142\/9789812799890_0008"},{"unstructured":"Roberts, F.S.: Society for Industrial, and Applied Mathematics. Graph Theory and Its Applications to Problems of Society. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (1978)","key":"837_CR38"},{"issue":"1","key":"837_CR39","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1137\/S0895480191223178","volume":"7","author":"D Sakai","year":"1994","unstructured":"Sakai, D.: Labeling chordal graphs: distance two condition. SIAM J. Discrete Math. 7(1), 133\u2013140 (1994). https:\/\/doi.org\/10.1137\/S0895480191223178","journal-title":"SIAM J. Discrete Math."},{"key":"837_CR40","first-page":"189","volume":"221","author":"A Shuchat","year":"2014","unstructured":"Shuchat, A., Shull, R., Trenk, A.N., West, L.C.: Unit mixed interval graphs. Congressus Numerantium 221, 189\u2013223 (2014)","journal-title":"Congressus Numerantium"},{"issue":"3","key":"837_CR41","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1002\/jgt.22159","volume":"87","author":"A Talon","year":"2018","unstructured":"Talon, A., Kratochv\u00edl, J.: Completion of the mixed unit interval graphs hierarchy. J. Graph Theory 87(3), 317\u2013332 (2018). https:\/\/doi.org\/10.1002\/jgt.22159","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00837-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00837-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00837-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T11:38:08Z","timestamp":1637321888000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00837-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,2]]},"references-count":41,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["837"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00837-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,9,2]]},"assertion":[{"value":"11 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}