Optimal Homologous Cycles, Total Unimodularity, and Linear Programming
Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy · SIAM Journal on Computing · 2011
Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer ($\mathbb{Z}$) coefficients, we show the following (Theorem 5.2): For a finite simplicial complex K of dimension greater than p, the boundary matrix $[\partial_{p+1}]$ is totally unimodular if and only if $H_p(L, L_0)$ is torsion-free for all pure subcomplexes $L_0, L$ in K of dimensions p and $p+1$, respectively, where $L_0 \subsetL$. Because of the total unimodularity of the boundary matrix, we can solve the optimization problem, which is inherently an integer programming problem, as a linear program and obtain an integer solution. Thus, the problem of finding optimal cycles in a given homology class can be solved in polynomial time. This result is surprising in the backdrop of a recent result which says that the problem is NP-hard under $\mathbb{Z}_2$ coefficients which, being a field, is in general easier to deal with. Our result implies, among other things, that one can compute in polynomial time an optimal $(d-1)$-cycle in a given homology class for any triangulation of an orientable compact d-manifold or for any finite simplicial complex embedded in $\mathbb{R}^d$. Our optimization approach can also be used for various related problems, such as finding an optimal chain homologous to a given one when these are not cycles. Our result can also be viewed as providing a topological characterization of total unimodularity.