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^*(2^{o(n)})$-time algorithm for PMC even when restricted to $n$-vertex bipartite graphs, and also show that PMC can be solved in $O^*(1.2721^n)$ time by means of an exact branching algorithm.


翻译:在一个图表中, 完美的匹配剪切是一个完美匹配的边缘切分。 完美的匹配切切( PMC) 是决定一个特定图表是否有一个完美的匹配切切, 并已知是 NP 完整的问题。 我们重新审视问题, 并显示, 当限制在最高高度3 和任意大的双边图时, PMC 仍然为 NP 完整。 补充这一硬性结果, 我们给出了两种图形类别, PMC 是多元时间可溶的。 第一个包括没有引导路径的爪状图和图, 第二个包含所有圆形图 。 假设指数时间 Hypothesis, 我们显示即使限制在 $n$- verex bipartite 图形时, PMC 也不存在美元( 1. 2721 nn) 的时间算法, 并显示 PMC 可以用精确的分支算法解决 $O ⁇ ( 1. 1.210 ) 。

0
下载
关闭预览

相关内容

《普适与移动计算期刊》(PMC)是一本高影响力、同行评议的技术期刊,它发表了高质量的科学文章,涵盖了普适与移动计算和系统的所有方面。官网链接:https://www.sciencedirect.com/journal/pervasive-and-mobile-computing/about/aims-and-scope
【经典书】C语言傻瓜式入门(第二版),411页pdf
专知会员服务
51+阅读 · 2020年8月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
3+阅读 · 2019年4月12日
Arxiv
0+阅读 · 2021年9月14日
Arxiv
0+阅读 · 2021年9月14日
Arxiv
0+阅读 · 2021年9月13日
Arxiv
0+阅读 · 2021年9月11日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
3+阅读 · 2019年4月12日
相关论文
Top
微信扫码咨询专知VIP会员