Problem statement : given a simplicial complex with weights on its simplices, and a chain, find the chain with minimal weight which is homologous to the given one. For example the shortest one. Or one with smallest support. With mod 2 coefficients (1 if a simplex is included, 0 if not) the problem has been known to be NP-hard. We show that if integer coefficients are used instead, the problem can be solved in polynomial time for a large class of simplicial complexes. Our main result is a theorem characterizing precisely when the boundary matrix of a simplicial complex is totally unimodular. Total unimodularity allows us to solve the problem using linear programming, while achieving integer solutions. Thus our main result is a topological characterization of total unimodularity of boundary constraints. The geometric meaning has been known in linear programming for over 50 years. Joint work with Tamal Dey and Bala Krishnamoorthy.
The preliminary paper Optimal Homologous Cycles, Total Unimodularity, and Linear Programming DOI: 10.1145/1806689.1806721, appeared in STOC 2010 the 42nd ACM Symposium on Theory of Computing. A more recent version with new results about Moebius complexes is here. The new results are part of our SIAM Journal on Computing paper (to appear).