# [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

Regards
Anil Hirani

--------------------------------------------------------------
Anil N. Hirani
Assistant Professor of Computer Science
University of Illinois at Urbana-Champaign
http://www.cs.illinois.edu/hirani
Office:  (217) 333-2727