Hardness Results for Homology Localization

Chen, Chao ; Freedman, Daniel

HP Development Company

关键词: algebraic topology;    homology;    localization;   

RP-ID  :  HPL-2009-374

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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.