Kratochvíl, Jan ;
Masařík, Tomáš ;
Novotná, Jana
UBubble 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, semiclosed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not clawfree, 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 subexponentialtime algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomialtime 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 upperbound on the cliquewidth 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 = {{UBubble 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:157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12724},
URN = {urn:nbn:de:0030drops127247},
doi = {10.4230/LIPIcs.MFCS.2020.57},
annote = {Keywords: Interval Graphs, Mixed Unit Interval Graphs, MaxCut Problem, Clique Width, Subexponential Algorithm, Bubble Model}
}
18.08.2020
Keywords: 

Interval Graphs, Mixed Unit Interval Graphs, MaxCut Problem, Clique Width, Subexponential Algorithm, Bubble Model 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 