## April 16, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
Optimal Homologous Cycles, Total Unimodularity, and Linear
Programming

## Bala Krishnamoorthy, Washington State University

Presenting his paper from
http://arxiv.org/abs/1001.0338

Abstract:
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 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$. 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 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. One consequence of our result, among others, is
that one can compute in polynomial time an optimal 2-cycle in a given
homology class for any finite simplicial complex embedded in
$\mathbb{R}^3$. 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.