Matching Cut in Graphs with Large Minimum Degree
Chi‐Yeh Chen, Sun‐Yuan Hsieh, Hoang-Oanh Le, Van Bang Lê, Sheng-Lung Peng
Abstract
Abstract In a graph, a matching cut is an edge cut that is a matching. M atching C ut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -complete. While M atching C ut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , M atching C ut is $${\mathsf {NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -complete in the class of graphs with minimum degree c and this restriction of M atching C ut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , M atching C ut remains $${\mathsf {NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -complete in the class of n -vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>></mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> . We give an exact branching algorithm to solve M atching C ut for graphs with minimum degree $$\delta \ge 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> in $$O^*(\lambda ^n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>O</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>λ</mml:mi> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> time, where $$\lambda$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>λ</mml:mi> </mml:math> is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>x</mml:mi> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>-</mml:mo> <mml:msup> <mml:mi>x</mml:mi> <mml:mi>δ</mml:mi> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . Despite the hardness results, this is a very fast exact exponential-time algorithm for M atching C ut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>O</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>.</mml:mo> <mml:msup> <mml:mn>0099</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> on graphs with minimum degree $$\delta \ge 469$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>469</mml:mn> </mml:mrow> </mml:math> . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo><</mml:mo> <mml:mi>c</mml:mi> <mml:mo><</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> and $$c^{\prime }\ge 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>c</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , M atching C ut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>≥</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>c</mml:mi> </mml:mfrac> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:msup> <mml:mi>c</mml:mi> <mml:mo>′</mml:mo> </mml:msup> </mml:mrow> </mml:math> .