Document Open Access Logo

Complexity of Maximum Cut on Interval Graphs

Authors Ranendu Adhikary , Kaustav Bose , Satwik Mukherjee, Bodhayan Roy

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.7.pdf
  • Filesize: 0.68 MB
  • 11 pages

Document Identifiers

Author Details

Ranendu Adhikary
  • Department of Mathematics, Jadavpur University, Kolkata, India
Kaustav Bose
  • Department of Mathematics, Jadavpur University, Kolkata, India
Satwik Mukherjee
  • Department of Mathematics, Jadavpur University, Kolkata, India
Bodhayan Roy
  • Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur, India

Funding

  • Adhikary, Ranendu: supported by Council of Scientific and Industrial Research (CSIR), Govt. of India.
  • Bose, Kaustav: supported by National Board for Higher Mathematics (NBHM), Department of Atomic Energy (DAE), Govt. of India.
  • Mukherjee, Satwik: supported by Council of Scientific and Industrial Research (CSIR), Govt. of India.
  • Roy, Bodhayan: supported by an ISIRD Grant from Sponsored Research and Industrial Consultancy, IIT Kharagpur.

Acknowledgements

We would like to thank the anonymous reviewers for their comments and suggestions which helped us to improve the paper.

Cite AsGet BibTex

Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of Maximum Cut on Interval Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.7

Abstract

We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Maximum cut
  • Interval graph
  • NP-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Katerina Asdre, Kyriaki Ioannidou, and Stavros D. Nikolopoulos. The harmonious coloring problem is NP-complete for interval and permutation graphs. Discret. Appl. Math., 155(17):2377-2382, 2007. URL: https://doi.org/10.1016/j.dam.2007.07.005.
  2. Francisco Barahona. The max-cut problem on graphs not contractible to K₅. Operations Research Letters, 2(3):107-111, 1983. URL: https://doi.org/10.1016/0167-6377(83)90016-0.
  3. Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36(3):493-513, 1988. Google Scholar
  4. Piotr Berman and Marek Karpinski. On some tighter inapproximability results. In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 200-209. Springer, 1999. URL: https://doi.org/10.1007/3-540-48523-6_17.
  5. Hans L. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs. Inf. Process. Lett., 31(3):135-138, 1989. URL: https://doi.org/10.1016/0020-0190(89)90221-4.
  6. Hans L. Bodlaender, Celina M. H. de Figueiredo, Marisa Gutierrez, Ton Kloks, and Rolf Niedermeier. Simple max-cut for split-indifference graphs and graphs with few P₄s. In Celso C. Ribeiro and Simone L. Martins, editors, 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, pages 87-99. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24838-5_7.
  7. Hans L Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1):14-31, 2000. Google Scholar
  8. Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. SIMPLE MAX-CUT for unit interval graphs and graphs with few P₄s. Electron. Notes Discret. Math., 3:19-26, 1999. URL: https://doi.org/10.1016/S1571-0653(05)80014-9.
  9. Arman Boyaci, Tínaz Ekim, and Mordechai Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Inf. Process. Lett., 121:29-33, 2017. URL: https://doi.org/10.1016/j.ipl.2017.01.007.
  10. Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 7:1-7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.7.
  11. K. C. Chang and David Hung-Chang Du. Efficient algorithms for layer assignment problem. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 6(1):67-78, 1987. URL: https://doi.org/10.1109/TCAD.1987.1270247.
  12. Maw-Shang Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput., 27(6):1671-1694, 1998. URL: https://doi.org/10.1137/S0097539792238431.
  13. Joel E Cohen and David W Stephens. Food webs and niche space. Princeton University Press, 1978. Google Scholar
  14. Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, and Gregory Kucherov. Optimal linear arrangement of interval graphs. In Rastislav Kralovic and Pawel Urzyczyn, editors, 31st International Symposium on Mathematical Foundations of Computer Science, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 267-279. Springer, 2006. URL: https://doi.org/10.1007/11821069_24.
  15. Josep Díaz and Marcin Kaminski. MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theor. Comput. Sci., 377(1-3):271-276, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.013.
  16. Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3):914-944, 2017. URL: https://doi.org/10.1007/s00453-016-0184-1.
  17. Michael R Garey and David S Johnson. A guide to the theory of NP-completeness. Computers and Intractability, pages 37-79, 1990. Google Scholar
  18. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  19. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Elsevier, 2004. Google Scholar
  20. Venkatesan Guruswami. Maximum cut on line and total graphs. Discret. Appl. Math., 92(2-3):217-221, 1999. URL: https://doi.org/10.1016/S0166-218X(99)00056-6.
  21. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput., 4(3):221-225, 1975. URL: https://doi.org/10.1137/0204019.
  22. Hiroshi Imai and Takao Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. Journal of Algorithms, 4(4):310-323, 1983. URL: https://doi.org/10.1016/0196-6774(83)90012-3.
  23. David S Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 6(3):434-451, 1985. URL: https://doi.org/10.1016/0196-6774(85)90012-4.
  24. John R Jungck, Gregg Dick, and Amy Gleason Dick. Computer-assisted sequencing, interval graphs, and molecular evolution. Biosystems, 15(3):259-273, 1982. URL: https://doi.org/10.1016/0303-2647(82)90010-7.
  25. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  26. J. Mark Keil. Finding hamiltonian circuits in interval graphs. Inf. Process. Lett., 20(4):201-206, 1985. URL: https://doi.org/10.1016/0020-0190(85)90050-X.
  27. Subhash Khot. On the power of unique 2-prover 1-round games. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775. ACM, 2002. URL: https://doi.org/10.1145/509907.510017.
  28. Jan Kratochvíl, Tomás Masarík, and Jana Novotná. U-bubble model for mixed unit interval graphs and its applications: The maxcut problem revisited. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 57:1-57:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.57.
  29. Chin Lung Lu and Chuan Yi Tang. A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inf. Process. Lett., 61(2):107-111, 1997. URL: https://doi.org/10.1016/S0020-0190(96)00193-7.
  30. Madhav V. Marathe, R. Ravi, and C. Pandu Rangan. Generalized vertex covering in interval graphs. Discret. Appl. Math., 39(1):87-93, 1992. URL: https://doi.org/10.1016/0166-218X(92)90116-R.
  31. Dániel Marx. A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett., 33(4):382-384, 2005. URL: https://doi.org/10.1016/j.orl.2004.07.006.
  32. Peisen Zhang, Eric A Schon, Stuart G Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler, and Philip E Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Bioinformatics, 10(3):309-317, 1994. URL: https://doi.org/10.1093/bioinformatics/10.3.309.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact