Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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. A recent result showed that this problem is NP-hard when the homology is defined using binary coefficients, which is intuitive and easy to deal with. In this paper we consider homology defined with integer coefficients. We show that the boundary matrix of a finite simplicial complex is totally unimodular if and only if the simplicial complex is relatively torsion-free with the homology defined relative to all pure subcomplexes of appropriate dimensions. 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. One consequence of our result, among others, is 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 d-dimensional space. Our optimization approach can also be used for various related problems, such as finding an optimal chain to a given one when these are not cycles.

This is joint work with Tamal Dey at Ohio State University and Anil Hirani at University of Illinois. The paper is available on arXiv: http://arxiv.org/abs/1001.0338.