Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bipartite graphs on which the number of perfect matchings can becomputed efficiently, based on a result of Little, by McCuaig et al. in 1999.In this paper we generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. We introducea version of Erdos-Posa property for matching minors and find a direct link between this property and planarity. From this, it follows that a class of bipartite graphs withperfect matchings has bounded perfect matching width if and only if it excludes aplanar matching minor. We also present algorithms for bipartite graphs of bounded perfect matching width for a matching version of the disjoint paths problem, matching minor containment, and for counting the number of perfect matchings. From our structural results, we obtain that recognising whether a bipartite graphGcontains afixed planar graphHas a matching minor, and that counting the number of perfect matchings of a bipartite graph that excludes a fixed planar graph as a matching minor are both polynomial time solvable.


翻译:匹配未成年人是适合使用完美匹配的图形的未成年人的一种特殊特征。 匹配未成年人的概念被用于对双边图形进行结构性描述, 其上根据1999年由McCuaig等人(Little)和McCuaig等人(McCuaig等人)得出的结果, 能够有效地对完美匹配的数量进行匹配。 在本文中, 我们把由Robertson和Seymour( Robertson and Seymour) 绘制的图小系列中的基本想法概括到有完美匹配的双边图形的设置。 我们为匹配未成年人和找到此属性与计划之间的直接联系。 从结构结果中, 我们了解到, 有完美匹配的双方图形Gcontains( perperfects) 相匹配的双边图形将完美匹配宽度捆绑在一起, 只要它排除一个平面图的最小匹配比例图, 我们也会为匹配的双面平面图表的匹配数字。

0
下载
关闭预览

相关内容

【微众银行】联邦学习白皮书_v2.0,48页pdf,
专知会员服务
165+阅读 · 2020年4月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【AAAI2020知识图谱论文概述】Knowledge Graphs @ AAAI 2020
专知会员服务
133+阅读 · 2020年2月13日
17篇知识图谱Knowledge Graphs论文 @AAAI2020
专知会员服务
171+阅读 · 2020年2月13日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
已删除
将门创投
4+阅读 · 2018年5月31日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月26日
The complexity of the Bondage problem in planar graphs
VIP会员
相关VIP内容
相关资讯
已删除
将门创投
4+阅读 · 2018年5月31日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员