Matching Cut in Graphs with Large Minimum Degree

Chi Yeh Chen, Sun Yuan Hsieh, Hoang Oanh Le, Van Bang Le, Sheng Lung Peng

研究成果: Article同行評審

摘要

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. While Matching Cut is trivial for graphs with minimum degree at most one, it is NP-complete on graphs with minimum degree two. In this paper, we show that, for any given constant c> 1 , Matching Cut is NP-complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant ϵ> 0 , Matching Cut remains NP-complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree δ> n1-ϵ. We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree δ≥ 3 in On) time, where λ is the positive root of the polynomial xδ+1- xδ- 1. Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is O(1. 0099 n) on graphs with minimum degree δ≥ 469. Complementing our hardness results, we show that, for any two fixed constants 1 < c< 4 and c≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree δ≥1cn-c′.

原文English
頁(從 - 到)1238-1255
頁數18
期刊Algorithmica
83
發行號5
DOIs
出版狀態Published - 2021 五月

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

指紋 深入研究「Matching Cut in Graphs with Large Minimum Degree」主題。共同形成了獨特的指紋。

引用此