Matching Cut in Graphs with Large Minimum Degree

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationComputing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
EditorsZhenhua Duan, Cong Tian, Ding-Zhu Du
PublisherSpringer Verlag
Pages301-312
Number of pages12
ISBN (Print)9783030261757
DOIs
Publication statusPublished - 2019 Jan 1
Event25th International Computing and Combinatorics Conference, COCOON 2019 - Xi'an, China
Duration: 2019 Jul 292019 Jul 31

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11653 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Computing and Combinatorics Conference, COCOON 2019
CountryChina
CityXi'an
Period19-07-2919-07-31

Fingerprint

Minimum Degree
Graph in graph theory
Hardness
Polynomials
NP-complete problem
Exponential time
Bipartite Graph
Branching
Polynomial time
Trivial
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hsieh, S-Y., Le, H. O., Le, V. B., & Peng, S. L. (2019). Matching Cut in Graphs with Large Minimum Degree. In Z. Duan, C. Tian, & D-Z. Du (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 / Zhenhua Duan ; Cong Tian ; Ding-Zhu Du. 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 = "Sun-Yuan Hsieh and Le, {Hoang Oanh} and Le, {Van Bang} and Peng, {Sheng Lung}",
year = "2019",
month = "1",
day = "1",
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 = "Zhenhua Duan and Cong Tian and Ding-Zhu Du",
booktitle = "Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings",
address = "Germany",

}

Hsieh, S-Y, Le, HO, Le, VB & Peng, SL 2019, Matching Cut in Graphs with Large Minimum Degree. in Z Duan, C Tian & D-Z Du (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. / 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 proceedingConference 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 -

Hsieh S-Y, Le HO, Le VB, Peng SL. Matching Cut in Graphs with Large Minimum Degree. In Duan Z, Tian C, Du D-Z, 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