License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.57
URN: urn:nbn:de:0030-drops-127247
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12724/
Kratochvíl, Jan ;
Masařík, Tomáš ;
Novotná, Jana
U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited
Abstract
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 - a 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 much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared 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 Boyaci, Ekim, and Shalom (2017). 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.
BibTeX - Entry
@InProceedings{kratochvl_et_al:LIPIcs:2020:12724,
author = {Jan Kratochv{\'\i}l and Tom{\'a}{\v{s}} Masař{\'\i}k and Jana Novotn{\'a}},
title = {{U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {57:1--57:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12724},
URN = {urn:nbn:de:0030-drops-127247},
doi = {10.4230/LIPIcs.MFCS.2020.57},
annote = {Keywords: Interval Graphs, Mixed Unit Interval Graphs, MaxCut Problem, Clique Width, Subexponential Algorithm, Bubble Model}
}
|
Keywords: |
|
Interval Graphs, Mixed Unit Interval Graphs, MaxCut Problem, Clique Width, Subexponential Algorithm, Bubble Model |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
