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.ISAAC.2016.50
URN: urn:nbn:de:0030-drops-68205
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6820/
Go to the corresponding LIPIcs Volume Portal

Le, Hoang-Oanh ; Le, Van Bang

On the Complexity of Matching Cut in Graphs of Fixed Diameter

pdf-format:
LIPIcs-ISAAC-2016-50.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{le_et_al:LIPIcs:2016:6820,
  author =	{Hoang-Oanh Le and Van Bang Le},
  title =	{{On the Complexity of Matching Cut in Graphs of Fixed Diameter}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{50:1--50:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6820},
  URN =		{urn:nbn:de:0030-drops-68205},
  doi =		{10.4230/LIPIcs.ISAAC.2016.50},
  annote =	{Keywords: matching cut, NP-hardness, graph algorithm, computational complexity, decomposable graph}
}

Keywords: matching cut, NP-hardness, graph algorithm, computational complexity, decomposable graph
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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