Matching Cut in Graphs with Large Minimum Degree

Sun Yuan Hsieh; Hoang Oanh Le; Van Bang Le; Sheng Lung Peng

doi:10.1007/978-3-030-26176-4_25

Matching Cut in Graphs with Large Minimum Degree

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

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

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	Ding-Zhu Du, Zhenhua Duan, Cong Tian
Publisher	Springer Verlag
Pages	301-312
Number of pages	12
ISBN (Print)	9783030261757
DOIs	https://doi.org/10.1007/978-3-030-26176-4_25
Publication status	Published - 2019
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/Territory	China
City	Xi'an
Period	19-07-29 → 19-07-31

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-26176-4_25

Cite this

Hsieh, S. Y., Le, H. O., Le, V. B., & Peng, S. L. (2019). Matching Cut in Graphs with Large Minimum Degree. In D-Z. Du, Z. Duan, & C. Tian (Eds.), Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings (pp. 301-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11653 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-26176-4_25

Hsieh, Sun Yuan ; Le, Hoang Oanh ; Le, Van Bang ; Peng, Sheng Lung. / Matching Cut in Graphs with Large Minimum Degree. Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings. editor / Ding-Zhu Du ; Zhenhua Duan ; Cong Tian. Springer Verlag, 2019. pp. 301-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5eaca0a47dce40b283118ba3c0e68f52,

title = "Matching Cut in Graphs with Large Minimum Degree",

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).",

author = "Hsieh, {Sun Yuan} and Le, {Hoang Oanh} and Le, {Van Bang} and Peng, {Sheng Lung}",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 25th International Computing and Combinatorics Conference, COCOON 2019 ; Conference date: 29-07-2019 Through 31-07-2019",

year = "2019",

doi = "10.1007/978-3-030-26176-4_25",

language = "English",

isbn = "9783030261757",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "301--312",

editor = "Ding-Zhu Du and Zhenhua Duan and Cong Tian",

booktitle = "Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings",

address = "Germany",

}

Hsieh, SY, Le, HO, Le, VB & Peng, SL 2019, Matching Cut in Graphs with Large Minimum Degree. in D-Z Du, Z Duan & C Tian (eds), Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11653 LNCS, Springer Verlag, pp. 301-312, 25th International Computing and Combinatorics Conference, COCOON 2019, Xi'an, China, 19-07-29. https://doi.org/10.1007/978-3-030-26176-4_25

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. / Ding-Zhu Du; Zhenhua Duan; Cong Tian. 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

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

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 - Du, Ding-Zhu

A2 - Duan, Zhenhua

A2 - Tian, Cong

PB - Springer Verlag

T2 - 25th International Computing and Combinatorics Conference, COCOON 2019

Y2 - 29 July 2019 through 31 July 2019

ER -

Hsieh SY, Le HO, Le VB, Peng SL. Matching Cut in Graphs with Large Minimum Degree. In Du D-Z, Duan Z, Tian C, editors, Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings. Springer Verlag. 2019. p. 301-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-26176-4_25

Matching Cut in Graphs with Large Minimum Degree

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this