Counting Perfect Matchings in Dense Graphs Is Hard
2025-05-06
0
0
132.62KB
3 页
10玖币
侵权投诉
Counting Perfect Matchings in Dense Graphs Is Hard
Nicolas El Maalouly Yanheng Wang
ETH Zürich, Switzerland
October 26, 2022
Abstract
We show that the problem of counting perfect matchings remains #P-complete even if we
restrict the input to very dense graphs, proving the conjecture in [5]. Here “dense graphs” refer
to bipartite graphs of bipartite independence number β62, or general graphs of independence
number α62. Our proof is by reduction from counting perfect matchings in bipartite graphs,
via elementary linear algebra tricks and graph constructions.
1 Notations and Technical Lemmas
First let us fix some notations.
•Problem Permanent(G): How many perfect matchings are there for a given graph G2 G?
• B: all bipartite graphs.
• B0: all complete bipartite graphs with potential parallel edges.
• B00: all (n¡3)-regular bipartite graphs.
• C: all graphs with independence number at most 2.
•f(n) := (n¡1)!! neven
0nodd counts the number of perfect matchings in Kn.
Towards our hardness results, we will study two special classes of square matrices. A main
technical tool is the following theorem from linear algebra.
Theorem 1. (Schur product theorem) If matrices M1; M2are positive definite, then their
entry-wise product M1◦M2is also positive definite.
Lemma 2. The matrix
An=0
B
B
B
B
B
B
@
0! 1! · · · n!
1! 2! · · · (n+ 1)!
·
·
··
·
··
···
·
·
n! (n+ 1)! · · · (2n)!
1
C
C
C
C
C
C
A
is positive definite for all n2N.
Proof. Let us index the rows and columns from 0to n. We pull out a factor of i!from each row i
and a factor of j!from each column j. This leaves us with a matrix A0where aij
0=(i+j)!
i!·j!=i+j
j.
It is a so-called symmetric Pascal matrix [4]. Observe that
i+j
j=X
k=0
ni
k j
j¡k=X
k=0
ni
kj
k
where the first equality follows from a thought experiment. Suppose we are electing jleaders out
from i+jcandidates. To implement this, divide the candidates into two fixed groups of sizes iand
j, respectively. We elect kleaders from the first group and the remaining j¡kfrom the second
group, for a varying parameter k.
Given the identity, it follows that
A0=L LTwhere `ik :=i
k:
1
摘要：
展开>>
收起<<
CountingPerfectMatchingsinDenseGraphsIsHardNicolasElMaaloulyYanhengWangETHZürich,SwitzerlandOctober26,2022AbstractWeshowthattheproblemofcountingperfectmatchingsremains#P-completeevenifwerestricttheinputtoverydensegraphs,provingtheconjecturein[5].Heredensegraphsrefertobipartitegraphsofbipartiteinde...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
2018年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2017年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2016年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2015年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2014年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2013年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2012年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 1 -
2010年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 4 -
2010-2020全国硕士研究生入学统一考试英语 考研英语一答案VIP免费
2024-12-02 2 -
2011年全国硕士研究生招生考试考研英语一真题VIP免费
2024-12-02 5
分类：图书资源
价格：10玖币
属性：3 页
大小：132.62KB
格式：PDF
时间：2025-05-06
作者详情
-
Adversarial and Safely Scaled Question Generation Sreehari Sankar Zhihang Dong October 19 202210 玖币0人下载
-
Adiabatic-impulse approximation in non-Hermitian Landau-Zener Model Xianqi Tong1Gao Xianlong2and Su-peng Kou1y 1Department of Physics Beijing Normal University Beijing 100000 Peoples Republic of China10 玖币0人下载
相关内容
-
2019年420联考《行测》真题（天津卷）答案及解析
分类：
时间：2025-05-02
标签：无
格式：PDF
价格：10 玖币
-
2019年420联考《行测》真题（四川上半年卷）答案及解析
分类：
时间：2025-05-02
标签：无
格式：PDF
价格：10 玖币
-
2019年420联考《行测》真题（内蒙古卷）答案及解析
分类：
时间：2025-05-02
标签：无
格式：PDF
价格：10 玖币
-
2019年420联考《行测》真题（广西卷）答案及解析
分类：
时间：2025-05-02
标签：无
格式：PDF
价格：10 玖币
-
2018年上海市公务员考试《行测》试卷（A卷）
分类：
时间：2025-05-02
标签：无
格式：PDF
价格：10 玖币
渝公网安备50010702506394
