TY - JOUR
T1 - Matching Cut in Graphs with Large Minimum Degree
AU - Chen, Chi Yeh
AU - Hsieh, Sun Yuan
AU - Le, Hoang Oanh
AU - Le, Van Bang
AU - Peng, Sheng Lung
N1 - Funding Information:
The authors are grateful to a reviewer for meticulous reading and helpful comments and suggestions. The fourth author thanks Ray Li (UNSW Sydney, Australia) for stimulating discussions on branching numbers.
Publisher Copyright:
© 2020, The Author(s).
PY - 2021/5
Y1 - 2021/5
N2 - 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 O∗(λn) 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′.
AB - 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 O∗(λn) 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′.
UR - http://www.scopus.com/inward/record.url?scp=85096439032&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096439032&partnerID=8YFLogxK
U2 - 10.1007/s00453-020-00782-8
DO - 10.1007/s00453-020-00782-8
M3 - Article
AN - SCOPUS:85096439032
SN - 0178-4617
VL - 83
SP - 1238
EP - 1255
JO - Algorithmica
JF - Algorithmica
IS - 5
ER -