2 Search Results for "Adhikary, Ranendu"

Document
DOI: 10.4230/LIPIcs.MFCS.2021.38
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, and Ana Silva

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{defigueiredo_et_al:LIPIcs.MFCS.2021.38,
  author =	{de Figueiredo, Celina M. H. and de Melo, Alexsander A. and Oliveira, Fabiano S. and Silva, Ana},
  title =	{{Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.38},
  URN =		{urn:nbn:de:0030-drops-144781},
  doi =		{10.4230/LIPIcs.MFCS.2021.38},
  annote =	{Keywords: maximum cut, interval graphs, interval lengths, interval count, NP-complete}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.7
Complexity of Maximum Cut on Interval Graphs

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

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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

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)

Copy BibTex To Clipboard

@InProceedings{adhikary_et_al:LIPIcs.SoCG.2021.7,
  author =	{Adhikary, Ranendu and Bose, Kaustav and Mukherjee, Satwik and Roy, Bodhayan},
  title =	{{Complexity of Maximum Cut on Interval Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.7},
  URN =		{urn:nbn:de:0030-drops-138067},
  doi =		{10.4230/LIPIcs.SoCG.2021.7},
  annote =	{Keywords: Maximum cut, Interval graph, NP-complete}
}
  • Refine by Author
  • 1 Adhikary, Ranendu
  • 1 Bose, Kaustav
  • 1 Mukherjee, Satwik
  • 1 Oliveira, Fabiano S.
  • 1 Roy, Bodhayan
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 2 NP-complete
  • 1 Interval graph
  • 1 Maximum cut
  • 1 interval count
  • 1 interval graphs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2021

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