Complexity and algorithms for Euler characteristic of simplicial complexes

DOI10.1016/J.JSC.2012.07.003MaRDI QIDQ1930164zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Bjarke Hammersholt Roune, Eduardo Saenz-de-Cabezon

Publication date 10 January 2013

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.4523

zbMATH Keywords

\(\#\text{P}\)-completealgorithmscomputational complexityEuler characteristicmonomial idealsimplicial complex

Mathematics Subject Classification ID

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)

Abstract: We consider the problem of computing the Euler characteristic of an abstract simplicial complex given by its vertices and facets. We show that this problem is #P-complete and present two new practical algorithms for computing Euler characteristic. The two new algorithms are derived using combinatorial commutative algebra and we also give a second description of them that requires no algebra. We present experiments showing that the two new algorithms can be implemented to be faster than previous Euler characteristic implementations by a large margin.

Recommendations

• 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

Cited in

(13)

• 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)