The Matching Cut is to decide if a graph has a matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a graph has a perfect matching that contains a matching cut. Both problems are NP-complete even for graphs of girth 5. However, it was open if they stay NP-complete for graphs of girth at least g, for every fixed $g\geq 6$. We solve both open problems by proving that this is indeed the case. Moreover, we give two new general hardness constructions, which imply that both problems are NP-complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with the one for Perfect Matching Cut, which is to decide if a graph has a perfect matching that is a matching cut.
翻译：匹配剪切是决定图形是否有匹配点, 是否匹配点也是边缘切口。 断开连接的完美匹配点问题在于决定图形是否有完美匹配点, 是否包含匹配点。 两个问题都是 NP- 完整, 甚至连5 girth 的图形都是 5 。 然而, 如果每个固定 $g\geq 6$ 的 Girth 图形都保持 NP- 完整, 则每个固定 $g\geq 6$ 的 Girth 图形都保持 NP- 完整 。 我们通过证明这确实属于这种情况来解决两个尚未解决的问题 。 此外, 我们给出了两个新的一般硬度构造, 这意味着当 H 含有至少 3 个水平两个顶点的连接部分时, H 问题都是 NP- 完成的 H- 无 H 图形 。 之后, 我们更新了无 H 图形的当前最先进的摘要, 并将其与“ 匹配点” 比较, 即决定一个图表是否有匹配点是否完美匹配点是匹配点 。
相关内容
微信扫码咨询专知VIP会员