The (Perfect) Matching Cut is to decide if a graph has a (perfect) 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 Matching Cut and Disconnected Perfect Matching are NP-complete even for graphs of girth 5, whereas Perfect Matching Cut is known to be NP-complete for graphs of arbitrarily large fixed girth. We prove the last result also for the other two problems, answering a question of Le and Le (TCS 2019) for Matching Cut. Moreover, we give three new general hardness constructions, which imply that all three 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 each other. Moreover, by combining our new hardness construction for Perfect Matching Cut with two existing results, we obtain a complete complexity classification of Perfect Matching Cut for H-subgraph-free graphs where H is any finite set of graphs.
翻译：匹配剪切( Perfect) 是要决定一个图形是否有一个( perfect) 匹配点, 也有一个边缘切分。 断开的完美匹配点是决定一个图形是否有一个包含匹配切分的完美匹配点。 匹配切分和断开的完美匹配点都是NP 完整的, 甚至连5 girth 5 的图形都是NP 。 而完美匹配切分已知是任意大固定盖的图形的NP 完全匹配。 我们证明了其他两个问题的最后结果, 回答匹配切分的 Le 和 Le 的问题( TCS 2019) 。 此外, 我们给出了三个新的一般硬度构造, 这意味着只要 H 含有两个顶点的连接组件, 并且至少 3 。 之后, 我们更新了无 H 图形的状态艺术摘要, 并相互比较 。 此外, 通过将我们用于 完美切切换的硬度构造与两个现有结果相结合, 我们获得了 H 子节截图的完美切分解点的完整复杂分类 。
相关内容
微信扫码咨询专知VIP会员