文章基本信息

标题：On the Complexity of Matching Cut in Graphs of Fixed Diameter
本地全文：下载
作者：Hoang-Oanh Le ; Van Bang Le
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：50:1-50:12
DOI：10.4230/LIPIcs.ISAAC.2016.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：matching cut; NP-hardness; graph algorithm; computational complexity; decomposable graph