The (Perfect) Matching Cut problem is to decide if a graph $G$ has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of $G$. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity results for both problems on special graph classes. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we introduce the Maximum Matching Cut problem. This problem is to determine a largest matching cut in a graph. We generalize and unify known polynomial-time algorithms for Matching Cut and Perfect Matching Cut restricted to graphs of diameter at most $2$ and to $(P_6 + sP_2)$-free graphs. We also show that the complexity of Maximum Matching Cut} differs from the complexities of Matching Cut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for $2P_3$-free quadrangulated graphs of diameter 3 and radius 2 and for subcubic line graphs of triangle-free graphs. In this way, we obtain full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and $H$-free graphs.
翻译：摘要：（完美）匹配割问题是决定一个图 $G$ 是否有一个（完美）匹配割，即一个连通的匹配使得 $G$ 与补图的交集为空。匹配割和完美匹配割都已知是 NP 完全问题，导致许多对于特定图类的复杂性结果。完美匹配割也是边数最多的匹配割。为了增加我们对两个问题之间关系的理解，我们引入了最大匹配割问题。该问题确定在一个图中最大的匹配割。我们推广并统一已知的针对直径不大于 $2$ 的图和 $(P_6 + sP_2)$-free 图的匹配割和完美匹配割的多项式时间算法。我们还证明了最大匹配割问题的复杂性与匹配割和完美匹配割的复杂性不同，通过证明对于直径为 $3$、半径为 $2$ 的 $2P_3$-free 四边形化图和三角形-自由图的亚立方线图，以及 $n$ 阶网格和 $n$ 阶网格 $-e$，最大匹配割问题是 NP 完全的。通过这种方式，我们获得了直径有界、半径有界和 $H$-free 图的最大匹配割问题的完整二分结论。
相关内容
微信扫码咨询专知VIP会员