[ALGTOP-L] Optimal Homologous Cycles, Total Unimodularity, and Linear Programming

Anil N. Hirani hirani at cs.illinois.edu
Tue Jan 5 12:00:56 EST 2010

I hope this will not be considered too out of place here --  this  
message is about our recent computational algebraic topology work.

We have just uploaded our paper "Optimal Homologous Cycles, Total  
Unimodularity, and Linear Programming", by Tamal K. Dey, Anil N.  
Hirani and Bala Krishnamoorthy, to arXiv at http://arxiv.org/abs/1001.0338

The problem we solve is this : 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. Assuming that the homology is  
defined with integer coefficients, we show the following : "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$ is a  
subset of $L$."

[A totally unimodular matrix is an integer matrix for which every  
square submatrix has determinant 1, -1, or 0. In linear programming  
the constraint polyhedron becomes integral if the constraint matrix is  
totally unimodular.]

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 integer solution.  
Thus the problem of finding optimal homologous chains can be solved in  
polynomial time for relatively torsion-free complexes.

This result is surprising in the backdrop of a recent result which  
says that the problem is NP-hard under $\mathbb{Z}_2$ coefficients.  
Also, the above torsion-free condition has not been studied before, in  
the context of this optimization problem.

One question for the mailing list -- is there a shorter, algebaric  
topology name for the torsion-free condition in our main result quoted  
above ? Has it been studied before in any context ? For example, the  
absence of a M\"obius like subcomplex (suitably generalized to higher  
dimensions) is a necessary condition for that torsion-free condition.

arXiv:1001.0338v1 [math.AT]
at http://arxiv.org/abs/1001.0338

Anil Hirani

Anil N. Hirani
Assistant Professor of Computer Science
University of Illinois at Urbana-Champaign
Office:  (217) 333-2727

More information about the ALGTOP-L mailing list