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. 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 (forumala presented), Matching Cut is NP -complete in the class of n-vertex (bipartite) graphs with minimum degree (forumala presented). We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree (forumala presented). This is a very fast exact exponential time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is (forumala presented). Complementing our hardness results, we show that, for any fixed constant (forumala presented), Matching Cut is solvable in polynomial time for graphs with very large minimum degree (forumala presented).
| Original language | English |
|---|---|
| Title of host publication | Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings |
| Editors | Zhenhua Duan, Cong Tian, Ding-Zhu Du |
| Publisher | Springer Verlag |
| Pages | 301-312 |
| Number of pages | 12 |
| ISBN (Print) | 9783030261757 |
| DOIs | |
| Publication status | Published - 2019 Jan 1 |
| Event | 25th International Computing and Combinatorics Conference, COCOON 2019 - Xi'an, China Duration: 2019 Jul 29 → 2019 Jul 31 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11653 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 25th International Computing and Combinatorics Conference, COCOON 2019 |
|---|---|
| Country | China |
| City | Xi'an |
| Period | 19-07-29 → 19-07-31 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
Matching Cut in Graphs with Large Minimum Degree. / Hsieh, Sun-Yuan; Le, Hoang Oanh; Le, Van Bang; Peng, Sheng Lung.
Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings. ed. / Zhenhua Duan; Cong Tian; Ding-Zhu Du. Springer Verlag, 2019. p. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11653 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Matching Cut in Graphs with Large Minimum Degree
AU - Hsieh, Sun-Yuan
AU - Le, Hoang Oanh
AU - Le, Van Bang
AU - Peng, Sheng Lung
PY - 2019/1/1
Y1 - 2019/1/1
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 (forumala presented), Matching Cut is NP -complete in the class of n-vertex (bipartite) graphs with minimum degree (forumala presented). We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree (forumala presented). This is a very fast exact exponential time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is (forumala presented). Complementing our hardness results, we show that, for any fixed constant (forumala presented), Matching Cut is solvable in polynomial time for graphs with very large minimum degree (forumala presented).
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 (forumala presented), Matching Cut is NP -complete in the class of n-vertex (bipartite) graphs with minimum degree (forumala presented). We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree (forumala presented). This is a very fast exact exponential time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is (forumala presented). Complementing our hardness results, we show that, for any fixed constant (forumala presented), Matching Cut is solvable in polynomial time for graphs with very large minimum degree (forumala presented).
UR - http://www.scopus.com/inward/record.url?scp=85070189553&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070189553&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-26176-4_25
DO - 10.1007/978-3-030-26176-4_25
M3 - Conference contribution
AN - SCOPUS:85070189553
SN - 9783030261757
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 301
EP - 312
BT - Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
A2 - Duan, Zhenhua
A2 - Tian, Cong
A2 - Du, Ding-Zhu
PB - Springer Verlag
ER -