Technical Reports


Click here for full text: PDF

Hardness Results for Homology Localization

Chen, Chao; Freedman, Daniel
HP Laboratories


Keyword(s): algebraic topology, homology, localization

Abstract: We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. Our work is restricted to homology over the Z2 field.

11 Pages

Additional Publication Information: To be published and presented at ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2010.

External Posting Date: December 17, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: December 17, 2009 [Fulltext]

Back to Index