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 pth homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each psimplex of K with a binary vector of length g with the following property: the annotations, summed over all psimplices in any pcycle 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 pcycles efficiently.
Using annotations of edges in 2complexes, 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 2skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1cycle is NPhard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.

Keywords: 
NPhard; Answering queries; Binary vectors; Coordinate vectors; homology basis; MAtrix multiplication; Optimal basis; optimal cycles; Pcycles; Simplicial complex; Time complexity

Conference Title:

SWAT: Symposium and Workshops on Algorithm Theory

Volume: 
7357

Conference Dates:

July 46, 2012

Conference Location:

Helsinki, Finland

ISBN:

9783642311543

Publisher:

Springer

Location:

Berlin, Germany

Date Published:

20120619

Start Page: 
189

End Page:

200

URL: 

DOI: 
1007/9783642311550_17

Open access: 
yes (repository) 