Document Open Access Logo

On the Complexity of Matching Cut in Graphs of Fixed Diameter

Authors Hoang-Oanh Le, Van Bang Le

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.50.pdf
  • Filesize: 476 kB
  • 12 pages

Document Identifiers

Author Details

Hoang-Oanh Le
Van Bang Le

Cite AsGet BibTex

Hoang-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 50:1-50:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.50

Abstract

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete even when restricted to bipartite graphs. It has been proved that Matching Cut is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d geq 4, Matching Cut is NP-complete in the class of graphs of diameter d. This almost resolves an open problem posed by Borowiecki and Jesse-Józefczyk in [Matching cutsets in graphs of diameter 2, Theoretical Computer Science 407 (2008) 574-582]. We then show that, for any fixed integer d geq 5, Matching Cut is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that Matching Cut is in polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving Matching Cut in graphs of diameter 2.
Keywords
  • matching cut
  • NP-hardness
  • graph algorithm
  • computational complexity
  • decomposable graph

Metrics

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

References

  1. Júlio Araújo, Nathann Cohen, Frédéric Giroire, and Frédéric Havet. Good edge-labelling of graphs. Discrete Applied Mathematics, 160(18):2502-2513, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.07.021.
  2. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308-340, 1991. URL: http://dx.doi.org/10.1016/0196-6774(91)90006-K.
  3. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121-123. Erratum: 14 (1982) 195, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90002-4.
  4. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: http://dx.doi.org/10.1137/S0097539793251219.
  5. Paul S. Bonsma. The complexity of the matching-cut problem for planar graphs and other graph classes. Journal of Graph Theory, 62(2):109-126, 2009. URL: http://dx.doi.org/10.1002/jgt.20390.
  6. Mieczyslaw Borowiecki and Katarzyna Jesse-Józefczyk. Matching cutsets in graphs of diameter 2. Theor. Comput. Sci., 407(1-3):574-582, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.07.002.
  7. Vasek Chvátal. Recognizing decomposable graphs. Journal of Graph Theory, 8(1):51-53, 1984. URL: http://dx.doi.org/10.1002/jgt.3190080106.
  8. Martin Davis and Hilary Putnam. A computing procedure for quantification theory. J. ACM, 7(3):201-215, 1960. URL: http://dx.doi.org/10.1145/321033.321034.
  9. David Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl., 3(3), 1999. URL: http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdf.
  10. David Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3):275-291, 2000. URL: http://dx.doi.org/10.1007/s004530010020.
  11. Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. URL: http://dx.doi.org/10.1137/0205048.
  12. Arthur M. Farley and Andrzej Proskurowski. Networks immune to isolated line failures. Networks, 12(4):393-403, 1982. URL: http://dx.doi.org/10.1002/net.3230120404.
  13. Ron L. Graham. On primitive graphs and optimal vertex assignments. Ann. N.Y. Acad. Sci., 175:170-186, 1970. URL: http://www.math.ucsd.edu/~ronspubs/70_04_primitive_graphs.pdf.
  14. Dieter Kratsch and Van Bang Le. Algorithms solving the matching cut problem. Theor. Comput. Sci., 609:328-335, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.10.016.
  15. Van Bang Le and Bert Randerath. On stable cutsets in line graphs. Theor. Comput. Sci., 1-3(301):463-475, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(03)00048-3.
  16. Augustine M. Moshi. Matching cutsets in graphs. Journal of Graph Theory, 13(5):527-536, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130502.
  17. Maurizio Patrignani and Maurizio Pizzonia. The complexity of the matching-cut problem. In Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001, Proceedings, pages 284-295, 2001. URL: http://dx.doi.org/10.1007/3-540-45477-2_26.
  18. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
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