Hardness Results for Optimal Homology Bases
Abstract
In this paper, we address the problem of localizing homology classes, namely, finding
the cycle representing a given class with the most concise geometric measure. We study
the problem with different measures: volume, diameter and radius. For volume, that
is, the 1-norm of a cycle, we prove the problem is NP-hard to approximate within any
constant factor. We also prove that for homology of 2-dimension or higher, the problem
is NP-hard to approximate even when the Betti number is O(1). A side effect is the
inapproximability proof of the problem of computing the nonbounding cycle with the
smallest volume, and computing cycles representing a homology basis with the minimal
total volume. As for the other two measures defined by pairwise geodesic distance, we
show that the localization problem is NP-hard for diameter, but is polynomial for
radius.