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

algorithmscomputational complexitysimplicial complexEuler characteristicmonomial ideal\(\#\text{P}\)-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Software, source code, etc. for problems pertaining to manifolds and cell complexes (57-04) 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) Abstract complexes in algebraic topology (55U05) Computational aspects and applications of commutative rings (13P99)

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

(11)

• scientific article; zbMATH DE number 3874104 (Why is no real title available?)
• Euler characteristic of abstract cubes complex
• Euler characteristic of the configuration space of a complex
• Surface-based computation of the Euler characteristic in the BCC grid
• The Euler characteristic of a polyhedral product
• The energy of a simplicial complex
• The complexity to compute the Euler characteristic of complex varieties
• Complexity of simplicial homology and independence complexes of chordal graphs
• Functions of finite simplicial complexes that are not locally determined
• Evasiveness through binary decision diagrams
• An algorithmic strategy for finding characteristic maps over wedged 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)