In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We ...
详细信息
In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We revisit the problem and show that PMC remains NP-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which PMC is polynomial-time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no O*(2o(n))-time algorithm for PMC even when restricted to n-vertex bipartite graphs, and also show that PMC can be solved in O*(1.2721n) time by means of an exact branching algorithm.(c) 2022 Elsevier B.V. All rights reserved.
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 fo...
详细信息
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 c > 1, Matching Cut is NP-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 Exponential-Time Hypothesis fails. We also show that, for any given constant. epsilon > 0, Matching Cut remains NP-complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree delta > n(1-epsilon). We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree delta >= 3 in O*(lambda(n)) time, where lambda is the positive root of the polynomial x(delta+1) - x(delta) - 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.0099(n)) on graphs with minimum degree delta >= 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 delta >= 1/c n - c'.
暂无评论