License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.38
URN: urn:nbn:de:0030-drops-144781
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14478/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-MFCS-2021-38.pdf (0.9 MB)

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.

BibTeX - Entry

@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.dagstuhl.de/opus/volltexte/2021/14478},
  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}
}

Keywords: maximum cut, interval graphs, interval lengths, interval count, NP-complete
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI