Document Open Access Logo

U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited

Authors Jan Kratochvíl , Tomáš Masařík , Jana Novotná

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.57.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Jan Kratochvíl
  • Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Tomáš Masařík
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
  • Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Jana Novotná
  • Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
  • Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Funding

Tomáš Masařík and Jana Novotná received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704, and from Charles University student grant SVV-2017-260452. Jan Kratochvíl was supported by grant GAČR 19-17314J of the Czech National Science Foundation.

Acknowledgements

The authors would like to thank Vít Jelínek for helpful comments. This paper is based on the master thesis of Jana Novotná.

Cite AsGet BibTex

Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.57

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Interval Graphs
  • Mixed Unit Interval Graphs
  • MaxCut Problem
  • Clique Width
  • Subexponential Algorithm
  • Bubble Model

Metrics

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

Related Versions

References

  1. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM, 62(5):1-25, November 2015. URL: https://doi.org/10.1145/2775105.
  2. 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.
  3. Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. SIMPLE MAX-CUT for unit interval graphs and graphs with few p_4s. Electronic Notes in Discrete Mathematics, 3:19-26, 1999. URL: https://doi.org/10.1016/S1571-0653(05)80014-9.
  4. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
  5. Arman Boyaci, Tinaz Ekim, and Mordechai Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29-33, 2017. URL: https://doi.org/10.1016/j.ipl.2017.01.007.
  6. Arman Boyaci, Tinaz Ekim, and Mordechai Shalom. The maximum cardinality cut problem in co-bipartite chain graphs. Journal of Combinatorial Optimization, 35(1):250-265, 2018. URL: https://doi.org/10.1007/s10878-015-9963-x.
  7. Personal communication with Adam Karczmarz, Wojciech Nadara, Anna Zych-Pawlewicz, and Pawel Rzazewski. Parameterized Algorithms Retreat of University of Warsaw 2019. Google Scholar
  8. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  9. Mitre C. Dourado, Van B. Le, Fábio Protti, Dieter Rautenbach, and Jayme L. Szwarcfiter. Mixed unit interval graphs. Discrete Mathematics, 312(22):3357-3363, 2012. URL: https://doi.org/10.1016/j.disc.2012.07.037.
  10. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width minimization is NP-hard. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 354-362, 2006. URL: https://doi.org/10.1145/1132516.1132568.
  11. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP-complete. SIAM Journal on Discrete Mathematics, 23(2):909-939, 2009. URL: https://doi.org/10.1137/070687256.
  12. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541-1563, January 2014. URL: https://doi.org/10.1137/130910932.
  13. Frédéric Gardi. The Roberts characterization of proper and unit interval graphs. Discrete Mathematics, 307(22):2906-2908, 2007. URL: https://doi.org/10.1016/j.disc.2006.04.043.
  14. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Computer Science and Applied Mathematics, XX:284, 1980. URL: https://doi.org/10.1016/C2013-0-10739-8.
  15. Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(3):423-443, 2000. URL: https://doi.org/10.1142/S0129054100000260.
  16. Pinar Heggernes, Daniel Meister, and Charis Papadopoulos. A new representation of proper interval graphs with an application to clique-width. Electronic Notes in Discrete Mathematics, 32:27-34, 2009. URL: https://doi.org/10.1016/j.endm.2009.02.005.
  17. Samuel B. Hopkins, Tselil Schramm, and Luca Trevisan. Subexponential lps approximate max-cut, 2019. URL: http://arxiv.org/abs/1911.10304.
  18. Felix Joos. A characterization of mixed unit interval graphs. Journal of Graph Theory, 79(4):267-281, 2015. URL: https://doi.org/10.1002/jgt.21831.
  19. Haim Kaplan and Ron Shamir. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM Journal on Computing, 25(3):540-561, 1996. URL: https://doi.org/10.1137/S0097539793258143.
  20. J. Mark Keil. Finding hamiltonian circuits in interval graphs. Information Processing Letters, 20(4):201-206, 1985. URL: https://doi.org/10.1016/0020-0190(85)90050-X.
  21. Minki Kim, Bernard Lidický, Tomáš Masařík, and Florian Pfender. Notes on complexity of packing coloring. Information Processing Letters, 137:6-10, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.012.
  22. Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-bubble model for mixed unit interval graphs and its applications: The maxcut problem revisited, 2020. URL: http://arxiv.org/abs/2002.08311.
  23. Vadim V. Lozin. Minimal classes of graphs of unbounded clique-width. Annals of Combinatorics, 15(4):707-722, October 2011. URL: https://doi.org/10.1007/s00026-011-0117-2.
  24. Dieter Rautenbach and Jayme Luiz Szwarcfiter. Unit interval graphs of open and closed intervals. Journal of Graph Theory, 72(4):418-429, 2013. URL: https://doi.org/10.1002/jgt.21650.
  25. F. S. Roberts. Indifference graphs. Proof Techniques in Graph Theory, pages 139-146, 1969. URL: https://ci.nii.ac.jp/naid/10025491782/en/.
  26. Denise Sakai. Labeling chordal graphs: Distance two condition. SIAM Journal of Discrete Mathematics, 7(1):133-140, 1994. URL: https://doi.org/10.1137/S0895480191223178.
  27. Alan Shuchat, Randy Shull, Ann N. Trenk, and Lee C. West. Unit mixed interval graphs. Congressus Numerantium, 221:189-223, 2014. Google Scholar
  28. Alexandre Talon and Jan Kratochvíl. Completion of the mixed unit interval graphs hierarchy. Journal of Graph Theory, 87(3):317-332, 2018. URL: https://doi.org/10.1002/jgt.22159.
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