Annotating simplices with a homology basis and its applications Conference Paper

Author(s): Busaryev, Oleksiy; Cabello, Sergio; Chen, Chao; Dey, Tamal K; Wang, Yusu
Title: Annotating simplices with a homology basis and its applications
Title Series: LNCS
Affiliation IST Austria
Abstract: Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω  + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.
Keywords: NP-hard; Answering queries; Binary vectors; Coordinate vectors; homology basis; MAtrix multiplication; Optimal basis; optimal cycles; P-cycles; Simplicial complex; Time complexity
Conference Title: SWAT: Symposium and Workshops on Algorithm Theory
Volume: 7357
Conference Dates: July 4-6, 2012
Conference Location: Helsinki, Finland
ISBN: 978-3-642-31154-3
Publisher: Springer  
Location: Berlin, Germany
Date Published: 2012-06-19
Start Page: 189
End Page: 200
DOI: 1007/978-3-642-31155-0_17
Open access: yes (repository)
IST Austria Authors
  1. Chao Chen
    14 Chen
Related IST Austria Work