Complexity and algorithms for Euler characteristic of simplicial complexes (Q1930164)

An abstract simplicial complex \(\Delta\) is a subset of the set of all subsets of a given finite set (the vertex set \(V\)) that is closed under taking subsets. The subsets of \(V\) that are in \(\Delta\) are called faces of the complex \(\Delta\). The inclusion-maximum faces of \(\Delta\) are called facets of \(\Delta\). Let \(\Delta \) be defined by two sets: the set of vertices and the set of facets. Actually, with such input, the problem of computing the Euler characteristic \(\chi (\Delta)\) has not been considered before in terms of complexity theory. The authors prove that this problem is \(\#\text{P}\)-complete by reducing to it the \(\#\text{SAT}\) problem (of counting the number of satisfying assignments of a given Boolean formula) well known to be \(\#\text{P}\)-complete. As a corollary they obtain a known result due to \textit{V. Kaibel} and \textit{M. E. Pfetsch} [in: Algebra, geometry, and software systems. Berlin: Springer. 23--48 (2003; Zbl 1027.65032)] stating that the problem of computing the \(f\)-vector of \(\Delta \) is \(\#\text{P}\)-hard. Furthermore, the authors present two algorithms for computing \(\chi (\Delta)\). The algorithms are presented in two forms: one is in terms of commutative algebra (based on monomial ideals) and one in terms of the complex \(\chi (\Delta)\) itself. Finally, the authors present the results of a set of simulation experiments to show that the two new algorithms run faster than previously known Euler characteristic algorithms.