  Given a simplicial complex K with weights on its simplices and a chain on it,
the Optimal Homologous Chain Problem (OHCP) is to find a chain with minimal
weight that is homologous (over the integers) to the given chain. The OHCP is
NP-complete, but if the boundary matrix of K is totally unimodular (TU), it
becomes solvable in polynomial time when modeled as a linear program (LP). We
define a condition on the simplicial complex called non total-unimodularity
neutralized, or NTU neutralized, which ensures that even when the boundary
matrix is not TU, the OHCP LP must contain an integral optimal vertex for every
input chain. This condition is a property of K, and is independent of the input
chain and the weights on the simplices. This condition is strictly weaker than
the boundary matrix being TU. More interestingly, the polytope of the OHCP LP
may not be integral under this condition. Still, an integral optimal vertex
exists for every right-hand side, i.e., for every input chain. Hence a much
larger class of OHCP instances can be solved in polynomial time than previously
considered possible. As a special case, we show that 2-complexes with trivial
first homology group are guaranteed to be NTU neutralized.
