Document Open Access Logo

Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete

Authors Celina M. H. de Figueiredo , Alexsander A. de Melo , Fabiano S. Oliveira , Ana Silva

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.38.pdf
  • Filesize: 0.89 MB
  • 15 pages

Document Identifiers

Author Details

Celina M. H. de Figueiredo
  • Federal University of Rio de Janeiro, Brazil
Alexsander A. de Melo
  • Federal University of Rio de Janeiro, Brazil
Fabiano S. Oliveira
  • Rio de Janeiro State University, Brazil
Ana Silva
  • Federal University of Ceará, Brazil

Funding

  • de Figueiredo, Celina M. H.: Partially funded by CNPq grants 302823/2016-6 and 407635/2018-1, CAPES Finance Code 001, and FAPERJ CNE E-26/202.793/2017.
  • de Melo, Alexsander A.: Partially funded by CNPq grant 140399/2017-8 and CAPES Finance Code 001.
  • Oliveira, Fabiano S.: Partially funded by FAPERJ grant E-26/010.002239/2019.
  • Silva, Ana: Partially funded by CNPq grants 303803/2020-7 and 437841/2018-9, and FUNCAP/CNPq grant 0112-00061.01.00/16.

Acknowledgements

We thank Vinicius F. Santos who shared Reference [Ranendu Adhikary et al., 2021], and anonymous referees for many valuable suggestions, including improving the interval count from 5 to 4.

Cite AsGet BibTex

Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira, and Ana Silva. Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.38

Abstract

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80’s, being one of the problems proposed by Johnson on his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still not known. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Graph theory
Keywords
  • maximum cut
  • interval graphs
  • interval lengths
  • interval count
  • NP-complete

Metrics

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

Related Versions

References

  1. Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of maximum cut on interval graphs. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 7:1-7:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.7.
  2. Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). 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.
  3. 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_4’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.
  4. Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. SIMPLE MAX-CUT for unit interval graphs and graphs with few p_4s. Electron. Notes Discret. Math., 3:19-26, 1999. URL: https://doi.org/10.1016/S1571-0653(05)80014-9.
  5. J. Adrian Bondy and Uppaluri S. R. Murty. Graph Theory. Graduate Texts in Mathematics. Springer, 2008. URL: https://doi.org/10.1007/978-1-84628-970-5.
  6. 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.
  7. Márcia R. Cerioli, Fabiano de S. Oliveira, and Jayme Luiz Szwarcfiter. The interval count of interval graphs and orders: a short survey. J. Braz. Comput. Soc., 18(2):103-112, 2012. URL: https://doi.org/10.1007/s13173-011-0047-1.
  8. 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.
  9. 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, Mathematical Foundations of Computer Science 2006, 31st International Symposium, 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.
  10. Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, and Alan P. Sprague. Simple linear time recognition of unit interval graphs. Inf. Process. Lett., 55(2):99-104, 1995. URL: https://doi.org/10.1016/0020-0190(95)00046-F.
  11. Celina M. H. de Figueiredo, João Meidanis, and Célia Picinin de Mello. A linear-time algorithm for proper interval graph recognition. Inf. Process. Lett., 56(3):179-184, 1995. URL: https://doi.org/10.1016/0020-0190(95)00133-W.
  12. Celina M.H. de Figueiredo, Alexsander A. de Melo, Diana Sasaki, and Ana Silva. Revising Johnson’s table for the 21st century. Discret. Appl. Math., 2021. URL: https://doi.org/10.1016/j.dam.2021.05.021.
  13. Tínaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof, and Daniel Meister. Computing minimum geodetic sets of proper interval graphs. In David Fernández-Baca, editor, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings, volume 7256 of Lecture Notes in Computer Science, pages 279-290. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-29344-3_24.
  14. Peter C. Fishburn. Interval graphs and interval orders. Discret. Math., 55(2):135-149, 1985. URL: https://doi.org/10.1016/0012-365X(85)90042-1.
  15. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  16. Yuan Jinjiang and Zhou Sanming. Optimal labelling of unit interval graphs. Applied Math., 10(3):337-344, September 1995. URL: https://doi.org/10.1007/bf02662875.
  17. David S. Johnson. The NP-completeness column: An ongoing guide. J. Algorithms, 6(3):434-451, 1985. URL: https://doi.org/10.1016/0196-6774(85)90012-4.
  18. Pavel Klavík, Yota Otachi, and Jirí Sejnoha. On the classes of interval graphs of limited nesting and count of lengths. Algorithmica, 81(4):1490-1511, 2019. URL: https://doi.org/10.1007/s00453-018-0481-y.
  19. 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.
  20. 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.
  21. Sara Nicoloso, Majid Sarrafzadeh, and X. Song. On the sum coloring problem on interval graphs. Algorithmica, 23(2):109-126, 1999. URL: https://doi.org/10.1007/PL00009252.
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