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

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 languageEnglish
Title of host publicationComputing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
EditorsDing-Zhu Du, Zhenhua Duan, Cong Tian
PublisherSpringer Verlag
Pages301-312
Number of pages12
ISBN (Print)9783030261757
DOIs
Publication statusPublished - 2019
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
Country/TerritoryChina
CityXi'an
Period19-07-2919-07-31

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Matching Cut in Graphs with Large Minimum Degree'. Together they form a unique fingerprint.

Cite this