Optimal Homologous Cycles, Total Unimodularity, and Linear Programming

Authors: Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy

Full paper: https://arxiv.org/abs/1001.0338

---

Introduction

Papers tackling OHCP in 2D surfaces:

• CHAMBERS, E. W., COLIN DE VERDI ‘ERE’ E., ERICKSON, J., LAZARUS, F., AND WHITTLESEY, K. Splitting (complicated) surfaces is hard. Comput. Geom. Theory Appl. 41 (2008), 94–110.
• CHAMBERS, E. W., ERICKSON, J., AND NAYYERI, A. Minimum cuts and shortest homologous cycles. In SCG ’09: Proc. 25th Ann. Sympos. Comput. Geom. (2009), pp. 377–385.
• CHEN, C., AND FREEDMAN, D. Measuring and computing natural generators for homology groups. Computational Geometry 43, 2 (2010), 169–181. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG’08).2
• COLIN DE VERDI ‘ERE’ E., AND ERICKSON, J. Tightening non-simple paths and cycles on surfaces. In SODA ’06: Proc. 17th Ann. ACM-SIAM Sympos. Discrete Algorithms (2006), pp. 192–201.
• DEY, T. K., LI, K., SUN, J., AND COHEN-STEINER, D. Computing geometry-aware handle and tunnel loops in 3d models. In SIGGRAPH ’08: ACM SIGGRAPH 2008 papers (New York, NY, USA, 2008), pp. 1–9.

Paper focus is on higher dimensional OHCP.

• Computing an optimal $p$-cycle under ${\mathbb{Z}}_2$ coefficients is NP-hard for $p\ge 1$
• Switching to $\mathbb{Z}$ make the problem polynomial time solvable for a large class of spaces
• An LP provides an integer solution iff constraint matrix is TU

Background

• A homomorphism between free abelian groups has a unique matrix representation with respect to a choice of bases
• $\{{\sigma }_i\}$ denotes oriented $(p-1)$-simplices in $K$
• $\{{\tau }_j\}$ denote oriented $p$-simplices in $K$
• Two $p$-chains $c$ and $c^{\prime }$ are homologous if $c=c^{\prime }+{\partial }_{d+1}d$ for some $d\in C_{p+1}(K)$
• A non-trivial cycle is a cycle not homologous to zero

Fundamental Theorem of Finitely Generated Abelian Groups

Any finitely generated abelian group $G$ can be written as a direct sum of two groups $G=F\oplus T$ where $F\cong (\mathbb{Z}\oplus \cdots \oplus \mathbb{Z})$ and $T\cong (\mathbb{Z}/t_1\oplus \cdots \oplus \mathbb{Z}/t_k)$ with $t_i>1$ and $t_i$ dividing $t_{i+1}$. The subgroup $T$ is called the torsion of $G$.

• A matrix is totally unimodular if the determinant of each square submatrix is 0, 1, or -1.

Theorem 2.1

Let $A$ be an $m\times n$ totally unimodular matrix and $b\in {\mathbb{Z}}^m$. Then the polyhedron $\mathcal{P}:=\{x\in {\mathbb{R}}^n\mid Ax=b,x\ge 0\}$ is integral, i.e., $\mathcal{P}$ is the convex hull of the integral vectors contained in $\mathcal{P}$. Similarly, the polyhedron $\mathcal{Q}:=\{x\in {\mathbb{R}}^n\mid Ax\ge b\}$ is integral.

• If $A$ is TU, then the ILP below can be solved in time polynomial in the dimensions of $A$ (use interior point method).

$$\min f^{\top }x\text{ subject to }Ax=b,x\ge 0\text{ and }x\in {\mathbb{Z}}^n$$

Problem Formulation

• For a vector $\text{v}\in {\mathbb{R}}^m$, the 1-norm $\Vert v{\Vert }_1$ is given by ${\sum }_i|v_i|$. If $W$ is an $m\times n$ nonsingular matrix, then $\Vert W\text{v}{\Vert }_1$ is called the weighted 1-norm of $\text{v}$.
• Problem statement:

Given a $p$-chain $\text{c}$ in $K$ and a diagonal matrix $W$ of appropriate dimension, the optimal homologous chain problem (OHCP) is to find a chain ${\text{c}}^{\ast }$ which has the minimal 1-norm $\Vert W{\text{c}}^{\ast }{\Vert }_1$ among all chains homologous to $\text{c}$.

• The above formulation is more general and allows modification of the objective by selecting an appropriate matrix $W$. For instance, if $W$ is a diagonal matrix with each non-zero entry being the Euclidean volume of a $p$-simplex, then we get the Euclidean ${\ell }^1$-optimization problem in which the optimal chain has the smallest $p$-dimensional volume amongst all homologous chains.

Optimal homologous chains and linear programming

Let $m=$ # $p$-simplices and $n=$ # $(p+1)$-simplices. Given an integer value $p$-chain $\text{c}$ the OHCP is:

$$\underset{\text{x},\text{y}}{\min }\Vert W\text{x}{\Vert }_1\text{ such that }\text{x}=\text{c}+[{\partial }_{p+1}]\text{y},\text{and }\text{x}\in {\mathbb{Z}}^m,\text{y}\in {\mathbb{Z}}^n.$$

One may rewrite this formulation to work over ${\mathbb{Z}}_2$ as follows:

$$\underset{\text{x},\text{y}}{\min }\Vert W\text{x}{\Vert }_1\text{ such that }\text{x}+2\text{u}=\text{c}+[{\partial }_{p+1}]\text{y},\text{and }\text{x}\in \{0,1{\}}^m,\text{u}\in {\mathbb{Z}}^m,\text{y}\in {\mathbb{Z}}^n.$$

Claim: A solution always exists

Proof: Suffices to show that

$$U_c=\{\Vert Wx{\Vert }_1\mid x=c+[{\partial }_{p+1}]y,x\in {\mathbb{Z}}^m\text{ and }y\in {\mathbb{Z}}^n\}$$

has a minimum. Define

$$U_c^{\prime }=\{\Vert Wx{\Vert }_1\mid \Vert Wx{\Vert }_1\le \Vert Wc{\Vert }_1,x=c+[{\partial }_{p+1}]y,x\in {\mathbb{Z}}^m\text{ and }y\in {\mathbb{Z}}^n\}\subseteq U_c$$

which must be finite as $x$ is integral. It is also non-empty as $c\in U_c^{\prime }$. Since $\inf U_c=\min U_c^{\prime }$, it follows that a solution exists.

• Below is the ILP formulation for the OHCP:

$$\begin{array}{rlr}& \min & \sum _i|w_i|(x_i^{+}+x_i^{-})\\ & \text{subject to}& {\text{x}}^{+}-{\text{x}}^{-}=\text{c}+[{\partial }_{p+1}]\text{y}\\ & & {\text{x}}^{+},{\text{x}}^{-}\ge 0\\ & & {\text{x}}^{+},{\text{x}}^{-}\in {\mathbb{Z}}^m,\text{y}\in {\mathbb{Z}}^n\end{array}$$

• The LP relaxation is the same with the exception of the integrality constraints being excluded
• In order to match Theorem 2.1, we replace $\text{y}$ with ${\text{y}}^{+}-{\text{y}}^{-}$. This leaves the constraint matrix to be $\left[\begin{array}{cccc}I& -I& -B& B\end{array}\right]$ where $B=[{\partial }_{p+1}]$.

Lemma 3.5

If $B$ is TU then so is $\left[\begin{array}{cccc}I& -I& -B& B\end{array}\right]$

• As a result:

Theorem 3.6

If the boundary matrix of a finite simpicial complex of dimension greater than $p$ is TU, the optimal homologous chain problem for $p$-chains can be solved in polynomial time.

• The above result does not hold in ${\mathbb{Z}}_2$ as the constraint matrix is different

Minimizing the number of simplices

• Setting $W$ to be the identity matrix gives ${\ell }^0$-optimization problem:

$$\min \Vert x{\Vert }_1\text{ such that }x=c+[{\partial }_{p+1}]y,x\in \{-1,0,1{\}}^m,y\in {\mathbb{Z}}^n.$$

Theorem 3.10

For any $p$-chain $c\in \{-1,0,1{\}}^m$, a solution to the ${\ell }^0$-optimization LP exists. Moreover, the optimal homologous chain $x^{\ast }$ has the smallest number of nonzero entries.

• Without the constraint $x\in \{-1,0,1{\}}^m$, we may get values outside of this range. Let $K$ be an hour-glass with boundary cycles $c_1$ and $c_2$ such that $c_1+c_2$ is not trivial. Let $z$ be the smallest cycle homologous to $c_1$ and $c_2$, i.e., $z=c_1+\partial y_1$ and $z=c_2+\partial y_2$. Then $c_1+c_2+\partial (y_1+y_2)=2z$, it follows that the chain homologus to $c_1+c_2$ has entries -2 or 2 for non-zero entries.
• LP Formulation:

$$\begin{array}{rlr}& \min & \sum _i(x_i^{+}+x_i^{-})\\ & \text{subject to}& {\text{x}}^{+}-{\text{x}}^{-}=\text{c}+[{\partial }_{p+1}]\text{y}\\ & & {\text{x}}^{+},{\text{x}}^{-}\ge 0\\ & & {\text{x}}^{+},{\text{x}}^{-}\le 1\end{array}$$

Theorem 3.13

If the boundary matrix $[{\partial }_{p+1}]$ of a finite simplicial complex of dimension greater than $p$ is TU, then given a $p$-chain with values in $\{-1,0,1\}$, a homologous $p$-chain with the smallest number of non-zeros taking values in $\{-1,0,1\}$ can be found in polynomial time.

Manifolds

In the remaining sections they focus on determining in which cases the boundary matrix is TU, starting with triangulations of orientable manifolds.

Orientable Manifolds

Herein, $K$ is a triangulation of a $(p+1)$-dimensional compact orientable manifold $M$.

Theorem 4.1

$[{\partial }_{p+1}]$ is TU for any orientation of simplices

Proof:

• Each $p$-face $\tau$ is a face of one or two $(p+1)$-simplices, hence the row of $[{\partial }_{p+1}]$ corresponding to $\tau$ has one or two nonzero entries.
  • If consistently oriented and two non-zero entries, they have alternating signs.
• A $\{-1,0,1\}$-matrix is TU if the columns have no more than two nonzero entries in which one is 1 and the other is -1.
• If $A^{\top }$ is TU, then $A$ is TU.
• Flipping the orientation can be done by multiplying its column by -1, which preserves TU.
• Any orientation can be made to be consistent by flipping the orientation of one or more simplices.

Non-orientable Manifolds

• Non-orientable manifolds are not guaranteed to have a TU boundary matrix.
• Let $K$ be a triangulation of a Mobius strip $M$. One may select rows and columns to obtain a boundary matrix which has a submatrix of determinant -2.
  • Said submatrix corresponds to relative boundary ${\partial }_2^{(L,L_0)}$ where $L=K$ and $L_0$ are the edges in $\partial M$.
• Note that $H_1(M)\cong \mathbb{Z}$ so the $H_1$ group has no torsion. But the relative homology $H_1(M,\partial M)$ does have torsion.

Simplicial Complexes

The following makes no use of geometric realization or embedding in ${\mathbb{R}}^n$ for the complexes. Hence, the following holds for abstract complexes.

Total Unimodularity and Relative Torsion

• They define a pure simplicial complex of dimension $p$ as a simplicial complex formed by a collection of $p$-simplices and their proper faces.
  • Triangulations of $p$-dimensional manifolds are pure simplicial complexes
  • A pure subcomplex is a subcompex that is pure.
• If $L\subset K$ and $L_0\subset L$ is a pure subcomplex of dimension $p$, then the matrix representing the relative boundary operator, ${\partial }_{p+1}^{(L,L_0)}:C_{p+1}(L,L_0)\to C_p(L,L_0)$, is obtained by including the columns of $[{\partial }_{p+1}]$ corresponding to the $(p+1)$-simplices in $L$ and excluding rows corresponding to the $p$-simplices n $L_0$ and any zero rows.

Theorem 5.2

$[{\partial }_{p+1}]$ is TU if and only if $H_p(L,L_0)$ is torsion-free, for all pure subcomplexes $L_0,L$ of $K$ of dimensions $p$ and $p+1$ respectively, where $L_0\subset L$.

Proof:

• $(\Rightarrow )$:
  • Proceed via contrapositve
  • Smith normal form on $[{\partial }_{p+1}^{(L,L_0)}]$ to get block matrix [D 0; 0 0] where $D=\text{diag}(d_1,\dots ,d_l)$.
  • Since $H_p(L,L_0)$ has torsion, $d_k>1$ for some $1\le k\le l$.
  • The product $d_1\cdots d_k$ is the gcd of the determinants of all $k\times k$ square submatrices.
  • $d_1\cdots d_k>1$, hence, there is a submatrix with absolute determinant greater than 1.
  • Thus, $[{\partial }_{p+1}]$ is not TU
• $(\Leftarrow )$
  • Proceed via contrapositive
  • Let $S$ be a square submatrix of $[{\partial }_{p+1}]$ such that $|\det (S)|>1$.
  • Let $L$ be the columns of $[{\partial }_p+1]$ in $S$ and $B_L$ the submatrix formed by columns $L$
  • Discard zero rows of $B_L$ to form submatrix $B_L^{\prime }$
  • Let $L_0$ correspond to rows of $B_L^{\prime }$ which are excluded to form $S$ to form matrix representation, $S$, of the relative boundary matrix.
  • At least one diagonal entry in the SNF of $S$ has magnitude greater than 1.
  • Hence $H_p(L,L_0)$ has torsion.

Corollary 5.4

Let $K$ be a simplicial complex with dimension greater than $p$. Then there is a polynomial time algorithm for answering the following question: Is $H_p(L,L_0)$ torsion-free for all subcomplexes $L_0$ and $L$ of dimensions $p$ and $(p+1)$ such that $L_0\subset L$?

Proof: Seymour’s decomposition theorem gives a polynomial time algorithm for deciding if a matrix is TU or not.

A Special Case

Theorem 5.7

If $K$ is a finite simplicial complex embedded in ${\mathbb{R}}^{d+1}$, then $H_d(L,L_0)$ is torsion-free for all pure subcomplexes $L_0$ of $L$ of dimensions $d$ and $d+1$ respectively, such that $L_0\subset L$.

Total Unimodularity and Mobius Complexes