Complexity of simplicial homology and independence complexes of chordal graphs

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.