Complexity and algorithms for Euler characteristic of simplicial complexes
\(\#\text{P}\)-completealgorithmscomputational complexityEuler characteristicmonomial idealsimplicial complex
Combinatorial aspects of simplicial complexes (05E45) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Computational aspects and applications of commutative rings (13P99) Abstract complexes in algebraic topology (55U05) Software, source code, etc. for problems pertaining to manifolds and cell complexes (57-04) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
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.
- Finding a simple polytope from its graph in polynomial time
- Compression with wildcards: Abstract simplicial complexes
- Convex hulls of \(f\)- and \(\beta\)-vectors
- On the complexity of the representation of simplicial complexes by trees
- On the computational complexity of Betti numbers: reductions from matrix rank
- Finding the convex hull facet by facet
- scientific article; zbMATH DE number 1961535
- Combinatorial face enumeration in convex polytopes
- The complexity to compute the Euler characteristic of complex varieties
- An algorithmic strategy for finding characteristic maps over wedged simplicial complexes
- The energy of a simplicial complex
- Euler characteristic of the configuration space of a complex
- Functions of finite simplicial complexes that are not locally determined
- scientific article; zbMATH DE number 3874104 (Why is no real title available?)
- Euler characteristic of abstract cubes complex
- The Euler characteristic of a polyhedral product
- Evasiveness through binary decision diagrams
- Surface-based computation of the Euler characteristic in the BCC grid
- Complexity of simplicial homology and independence complexes of chordal graphs
- Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
- Monomial polarization and depolarization of abstract simplicial complexes
This page was built for publication: Complexity and algorithms for Euler characteristic of simplicial complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1930164)
