标题： 匹配割和在有界半径和直径的二部图上的变体 显示英文标题

标题： Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter

摘要： 在匹配割问题中，我们询问图$G$是否有匹配割，即同时也是图$G$的边割的匹配。 我们考虑的变体包括完美匹配割和不连通完美匹配，我们询问是否存在一个匹配割分别等于、包含在一个完美匹配中。 此外，在最大匹配割问题中，我们要求具有最多边数的匹配割。 我们考虑的最后一个问题是$d$-Cut，我们要求一个边割，其中每个顶点在割中的边数至多为$d$。 我们研究了这些问题在有界半径和直径的二分图上的计算复杂性。 我们的结果扩展了已知的关于匹配割和不连通完美匹配的结果。 我们给出了$d$-Cut 和最大匹配割的复杂性二分法，并解决了不连通完美匹配中两个开放案例中的一个。 对于完美匹配割，我们给出了有界半径和直径的二分图上的第一个难解结果，并扩展了已知的多项式情况。 显示英文摘要

摘要： In the Matching Cut problem we ask whether a graph $G$ has a matching cut, that is, a matching which is also an edge cut of $G$. We consider the variants Perfect Matching Cut and Disconnected Perfect Matching where we ask whether there exists a matching cut equal to, respectively contained in, a perfect matching. Further, in the problem Maximum Matching Cut we ask for a matching cut with a maximum number of edges. The last problem we consider is $d$-Cut where we ask for an edge cut where each vertex is incident to at most $d$ edges in the cut. We investigate the computational complexity of these problems on bipartite graphs of bounded radius and diameter. Our results extend known results for Matching Cut and Disconnected Perfect Matching. We give complexity dichotomies for $d$-Cut and Maximum Matching Cut and solve one of two open cases for Disconnected Perfect Matching. For Perfect Matching Cut we give the first hardness result for bipartite graphs of bounded radius and diameter and extend the known polynomial cases.