Matching Cut in Graphs with Large Minimum Degree
- PDF / 1,495,658 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 109 Downloads / 211 Views
Matching Cut in Graphs with Large Minimum Degree Chi‑Yeh Chen1 · Sun‑Yuan Hsieh1 · Hoang‑Oanh Le2 · Van Bang Le3 · Sheng‑Lung Peng4 Received: 14 February 2020 / Accepted: 4 November 2020 © The Author(s) 2020
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 𝖭𝖯-complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is 𝖭𝖯-complete on graphs with minimum degree two. In this paper, we show that, for any given constant c > 1 , Matching Cut is 𝖭𝖯-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 ExponentialTime Hypothesis fails. We also show that, for any given constant 𝜖 > 0 , Matching Cut remains 𝖭𝖯-complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree 𝛿 > n1−𝜖 . We give an exact branching algorithm to solve Match∗ n ing Cut for graphs with minimum degree 𝛿 ≥ 3 in O (𝜆 ) time, where 𝜆 is the posi𝛿+1 𝛿 tive root of the polynomial x − 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.0099n ) 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 𝛿 ≥ 1c n − c�. Keywords Matching cut · Graph algorithm · Exact branching algorithm · NP-hard problem
A preliminary version [10] of this article has appeared in Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019), Lecture Notes in Computer Science 11653, pp. 301–312. * Van Bang Le van‑bang.le@uni‑rostock.de Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction In a graph G = (V, E) , a cut is a partition V = X ∪̇ Y of the vertex set into disjoint, non-empty sets X and Y, written (X, Y). The set of all edges in G having an endvertex in X and the other endvertex in Y, also written (X, Y), is called the edge cut of the cut (X, Y). A matching cut is an edge cut that is a (possibly empty) matching. Another way to define matching cuts is as follows [5, 9]. A partition V = X ∪̇ Y of the vertex set of the graph G = (V, E) into disjoint, non-empty sets X and Y, is a matching cut if and only if each vertex in X has at most one neighbor in Y and each vertex in Y has at most one neighbor in X. Graham [9] studied matching cuts in graphs in connection to a number theory problem called cube-numbering. In [6], Farley and Proskurowski studied matching cuts in the context of network applications. Patrignani and Pizzonia [18] pointed out an application of matching cuts in graph drawing. Matching cuts have been used by Araújo et al. [1] in studying good edge-labellings in the context of WDM
Data Loading...
