Complexity of simplicial homology and independence complexes of chordal graphs

详细信息    查看全文

• 作者：Michał Adamaszek^a ; ¹ ; ^{aszek@mimuw.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Juraj Stacho^b ; ² ; ^{stacho@cs.toronto.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Computational complexity ; Homology ; Clique complex ; Independence complex ; Chordal graph
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：57
• 期：Complete
• 页码：8-18
• 全文大小：399 K

文摘

We prove the NP-hardness of computing homology groups of simplicial complexes when the size of the input complex is measured by the number of maximal faces or the number of minimal non-faces. The latter case implies NP-hardness of the homology problem for clique and independence complexes of graphs.

Our approach is based on the observation that the homology of an independence complex of a chordal graph can be described using what we call strong induced matchings in the graph (also known as cross-cycles). We show that finding such a matching of a specified size in a chordal graph is NP-hard.

We further study the computational complexity of finding any cross-cycle in arbitrary and chordal graphs.