Efficient Network Flow Models for Optimal Homology Problems over the Integers

The following comments are based on the paper-main_v3_2025.tex version on Overleaf.

Overall impression: Either I lack the prerequisite knowledge to read this paper, or the paper is unnecessarily abstract.

---

• OHCP is NP-hard when working over $\mathbb{Z}$ or ${\mathbb{Z}}_2$.

  • Top dimensional complexes, $(d+1)$-complex in ${\mathbb{R}}^{d+1}$, is solvable in $O(N^{2.38}\log N)$ over $\mathbb{Z}$, where $N=O(dn)$.
  • The fastest algorithms for min-cost flow are almost linear: $O(E^{1+o(1)})$.

• Contributions:

  • Network flow model (min-cost flow) for OHPs over $\mathbb{Z}$ with $d$-cycles as input in ${\mathbb{R}}^{d+1}$ (codimension 1)
  • Non-negative flow model (${\mathbb{Z}}_{+}$-flow)

• Question: Why is the number of arcs not known apriori? “The number of arcs lies in the interval $[2m+{\beta }_d+1,2m+2{\beta }_d+1]$“

Background, Definitions, and Examples

• Alexander duality theorem: Let $\mathcal{K}$ be a $(d+1)$-complex with $\text{rank}{\mathcal{H}}_d(\mathcal{K})={\beta }_d$. Then ${\mathbb{R}}^{d+1}\setminus \lfloor \mathcal{K}\rfloor$ can be partitioned into ${\beta }_d+1$ voids $\mathcal{V}=\{{\nu }_0,{\nu }_1,\dots ,{\nu }_{{\beta }_d}\}$, where ${\nu }_0$ is the unbounded outer void. That is, $\mathcal{K}\cup \mathcal{V}={\mathbb{R}}^{d+1}$.

  • Bijection between generators of ${\mathcal{H}}_d(\mathcal{K})$, given by components of $\partial \mathcal{K}={\mathring{\mathbf{w}}}_0-{\sum }_{l=1}^{{\beta }_d}{\mathring{\mathbf{w}}}_l$, and inner voids of $\mathcal{K}$: ${\mathring{\mathbf{w}}}_l=\partial {\nu }_l$ and ${\mathring{\mathbf{w}}}_0\sim 0$ corresponds to the boundary of the outer void ${\mathring{\mathbf{w}}}_0=\partial {\nu }_0$.

• Question: Text states $\mathcal{K}\cup \mathcal{V}={\mathbb{R}}^{d+1}$, but Figure (2a) states that $\mathcal{K}\cup \mathcal{V}={\mathbb{S}}^{d+1}$.

• The $d$ and $(d+1)$-simplices of $\mathcal{K}$ are weighted by non-negative length-costs $c:{\mathcal{K}}_d\to {\mathbb{Z}}_{+}$ and area-costs $\alpha :{\mathcal{K}}_{d+1}\to {\mathbb{Z}}_{+}$.

  • Denoted $\mathbf{c}=(c_1,\dots ,c_m)$ and $\alpha =({\alpha }_1,\dots ,{\alpha }_n)$
  • We define $\alpha (\nu )=+\infty$ for all $\nu \notin {\mathcal{K}}_{d+1}$

• Cost functions:

$$|c(\mathbf{x})|=\sum _{e\in {\mathcal{K}}_d}c(e_i)\cdot |\mathbf{x}(e_i)|\ge 0\text{ and }|\alpha (\pi )|=\sum _{{\tau }_j\in {\mathcal{K}}_{d+1}}\alpha ({\tau }_j)\cdot |\pi ({\tau }_j)|\ge 0$$

• $d$-cochain $\mathbf{f}$ is $\mathbb{Z}$-valued homomorphism on $d$-simplices, $\mathbf{f}:{\mathcal{K}}_d\to \mathbb{Z}$.
  • Groups of $d$-chains and $d$-cochains are isomorphic, ${\mathcal{C}}_d(\mathcal{K})\cong {\mathcal{C}}^d(\mathcal{K})$
  • The $d$-coboundary operator ${\delta }_d:{\mathcal{C}}^{d-1}\to {\mathcal{C}}^d$ given by ${\delta }_d\mathbf{f}(\tau )=\mathbf{f}({\partial }_d\tau )$ for $\tau \in {\mathcal{K}}_d$.
  • Fundamental property of cohomology: ${\delta }_{d+1}\circ {\delta }_d=0$
  • The matrix representaiton is given by $[{\delta }_d]=[{\partial }_d{]}^{\top }$
• The generators of $d$-boundaries are in 1-to-1 correspondence with $(d+1)$-simplices: ${\mathring{\mathbf{w}}}_j\in [{\mathcal{B}}_d(\mathcal{K})]\iff {\mathring{\mathbf{w}}}_j={\partial }_{d+1}{\tau }_j$ for all ${\tau }_j\in {\mathcal{K}}_{d+1}$
• The homology and cohomology groups are isomorphics, ${\mathcal{H}}_d(\mathcal{K})\cong {\mathcal{H}}^d(\mathcal{K})$, hence $\text{rank}{\mathcal{H}}_d(\mathcal{K})=\text{rank}{\mathcal{H}}^d(\mathcal{K})={\beta }_d$
• Hodge decomposition: Given a simplicial complex $\mathcal{K}$,

$${\mathcal{C}}_d(\mathcal{K})\cong {\mathcal{B}}^d(\mathcal{K})\oplus {\mathcal{H}}_d(\mathcal{K})\oplus {\mathcal{B}}_d(\mathcal{K}).$$

• A $d$-cycle is called a flow and the relation ${\partial }_d\mathbf{z}=0$ for all $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ is called the flow conservation condition.
  • Likewise, a $d$-cocycle is called a coflow and ${\delta }_{d+1}\mathbf{f}=0$ for all cocycles $\mathbf{f}$ is called the circulation conservation condition.
  • One may view a $d$-coflow $\mathbf{f}$ as a function defined on $d$-cycles, $\mathbf{f}:{\mathcal{Z}}_d(\mathcal{K})\to \mathbb{Z}$, which maps $d$-boundaries to 0.
• Define the flux of $\mathbf{f}\in {\mathcal{Z}}^d(\mathcal{K})$ through $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$ by $|\mathbf{f}(\mathbf{z})|$
• Denote by $\{{\mathring{\mathbf{w}}}_1,\dots ,{\mathring{\mathbf{w}}}_{{\beta }_d}\}$ a set of simple cycles that generate ${\mathcal{H}}_d(\mathcal{K})$ and ${\mathring{\mathbf{w}}}_0={\partial }_{d+1}\mathcal{K}+{\sum }_{l=1}^{{\beta }_d}{\mathring{\mathbf{w}}}_l\sim 0$
• The homology signature of a $d$-cycle $\mathbf{z}$, is given by $[\mathbf{z}]=[{\zeta }_0,{\zeta }_1,\dots ,{\zeta }_{{\beta }_d}]$ where $\mathbf{z}\sim {\sum }_{l=0}^{{\beta }_d}{\zeta }_l\cdot {\mathring{\mathbf{w}}}_l$, where ${\zeta }_0=0$.

Question: What is the point of ${\mathring{\mathbf{w}}}_0$ if ${\zeta }_0$ is always zero?

• We define a $d$-copath from ${\mathbf{w}}^{\prime }$ to ${\mathbf{w}}^{\prime \prime }$, both in ${\mathcal{Z}}_d(\mathcal{K})$, to be a simple $d$-cochain $\mathbf{p}=\mathbf{p}({\mathbf{w}}^{\prime };{\mathbf{w}}^{\prime \prime })$ such that $\mathbf{p}({\mathbf{w}}^{\prime })=-1$ and $\mathbf{p}({\mathbf{w}}^{\prime \prime })=+1$ and is 0 for any other $d$-cycle.
  • If ${\mathbf{w}}^{\prime }={\partial }_{d+1}\eta$ and ${\mathbf{w}}^{\prime \prime }={\partial }_{d+1}\tau$, then ${\delta }_{d+1}\mathbf{p}=\tau -\eta$

Embedding and Dual Complex

• Denote by ${\mathcal{V}}_I=\mathcal{V}\setminus \{{\nu }_0\}$, i.e., the set of inner voids.

• Every embeddable complex is a weak pseudomanifold, i.e., every $(d-1)$-simplex has at most two cofaces.

• Embedability implies orientable

• We require the simplices of $\mathcal{K}$ to be consistently oriented:

  • If, two $(d+1)$-simplices $\eta ,\tau$ share a $d$-face $e=\eta \cap \tau$ then $e$ must be a positive face of one of them, and a negative face of the other, $\partial \tau (e)=-\partial \eta (e)$.
  • Assume $\partial \tau (e)=+1$ and $\partial \eta (e)=-1$. Then we denote the natural orientation of $e$ as $e=(\eta \uparrow \tau )$ with coboundary $\delta e=\tau -\eta$.
  • We call $\eta ={\delta }^{-}e$ and $\tau ={\delta }^{+}e$ the left and right coface of $e$ respectively.
  • By the left-hand rule, the positive faces of $\tau \in {\mathcal{K}}_{d+1}$ define a clockwise direction of curling along its boundary $\partial \tau$.

• A dual complex ${\mathcal{K}}^{\ast }$ of $\mathcal{K}\subset {\mathbb{R}}^{d+1}$ is given by the isomorphism ${\mathcal{C}}_q({\mathcal{K}}^{\ast };\mathbb{Z})\cong {\mathcal{C}}_{d-q+1}(\mathcal{K};\mathbb{Z})$ for $0\le q\le d+1$.

Comment: This is not clear to me.

• The idea of the dual complex is for the generators of ${\mathcal{Z}}_d(\mathcal{K})$ to be in one-to-one correspondence with dual nodes and two arcs are given for each orientation of connecting $(d+1)$-chains: $e_{+}^{\ast }=({\eta }^{\ast }\to {\tau }^{\ast })$ and $e_{-}^{\ast }=({\tau }^{\ast }\to {\eta }^{\ast })$ so that $e_{-}^{\ast }=-e_{+}^{\ast }$.

Comment: The above bullet is my understanding of Figure (3b).

• Define the acyclic complex $\overline{\mathcal{K}}=\mathcal{K}\cup \mathcal{V}$.
  • ${\mathcal{H}}_d(\overline{\mathcal{K}})=\{0\}$ as ${\mathcal{Z}}_d(\overline{\mathcal{K}})={\mathcal{B}}_d(\overline{\mathcal{K}})={\mathcal{Z}}_d(\mathcal{K})$
  • The $d$-th cohomology ${\mathcal{H}}^d(\overline{\mathcal{K}})$ is trivial, but ${\mathcal{Z}}^d(\mathcal{K})\ne {\mathcal{Z}}^d(\overline{\mathcal{K}})$
• Define the dual graph, ${\mathcal{K}}^{\ast }=({\overline{\mathcal{F}}}^{\ast },{\overline{\mathcal{E}}}^{\ast })$, as a 1-skeleton subcomplex of the dual complex ${\overline{\mathcal{K}}}^{\ast }$
  • The nodes correspond to $(d+1)$-simplices and voids: ${\overline{\mathcal{F}}}^{\ast }={\mathcal{F}}^{\ast }\cup {\mathcal{V}}^{\ast }$
  • For each oriented $d$-simplex $e=(\eta \uparrow \tau )$, $\eta ,\tau \in {\overline{\mathcal{K}}}_{d+1}$, we add arcs $e_{+}^{\ast }=({\eta }^{\ast }\to {\tau }^{\ast })$ and ${\tau }^{\ast }\to {\eta }^{\ast }$ with weights given by the length-volume $c(e)$
• We split the set of arcs ${\overline{\mathcal{E}}}^{\ast }$ into positive/natural arcs and negative/reversed arcs:
  • ${\vec{\mathcal{E}}}_{+}^{\ast }=\{e_{+}^{\ast }=({\eta }^{\ast }\to {\tau }^{\ast })\mid (\eta \uparrow \tau )\in {\overline{K}}_d\}$
  • ${\vec{\mathcal{E}}}_{-}^{\ast }=\{e_{-}^{\ast }=({\tau }^{\ast }\to {\eta }^{\ast })\mid (\eta \uparrow \tau )\in {\overline{K}}_d\}$

Network Flow Model for OHCP

• Given $d$-cycle $\mathbf{z}\in {\mathcal{Z}}_d(\mathcal{K})$, the OHCP seeks to find a $d$-cycle $\mathbf{x}\sim \mathbf{z}$ of minimal cost $|c(\mathbf{x})|$
• We want to ensure that for any extension of $\mathcal{K}$, the LP gives a feasible solution in $\mathcal{K}$. That is, $\mathbf{x}(\tilde{\sigma })=0$ and $\pi (\tilde{\nu })=0$ for any $\tilde{\sigma }\notin {\mathcal{K}}_d$ and $\tilde{\nu }\notin {\mathcal{K}}_{d+1}$.

Question: Where does the dual formulation come from?

• By the lemmas, any $d$-cycle in ${\mathcal{Z}}_d(\mathcal{K})$ is a $d$-boundary on ${\mathcal{B}}_d(\overline{\mathcal{K}})$.
• Define ${\text{dist}}_z\in {\mathcal{C}}_{d+1}(\overline{\mathcal{K}})$ such that ${\overline{\partial }}_{d+1}{\text{dist}}_z=\mathbf{z}$.
  • The values of ${\text{dist}}_z$ (known as $d$-winding number) measures the direction and how many times each $(d+1)$-facet is encircled by $\mathbf{z}$.
  • Positive values correspond to encircling in a clockwise direction, negative counter-clockwise.
  • Zero values correspond to the facets that are “outside” of $\mathbf{z}$.
• $[\mathbf{z}]=[{\zeta }_0,{\zeta }_1,\dots ,{\zeta }_{{\beta }_d}]=[{\text{dist}}_z({\nu }_0),{\text{dist}}_z({\nu }_1),\dots ,{\text{dist}}_z({\nu }_{{\beta }_d})]$

Question: Unsure what the point of this sentence on homology signature is.

• One can measure the cost of sending $k$ units of flow along a copath $\mathbf{p}=\mathbf{p}(\eta \to \tau )$ by the endpoints:

$${\text{cost}}_z(\mathbf{p};k)=k\cdot \mathbf{p}(\mathbf{z})=k\cdot ({\text{dist}}_z(\tau )-{\text{dist}}_z(\eta ))$$

• The max-bounding chain problem is dual to the shortest path distance problem on the dual graph with costs given by the input $d$-cycle.

• Define ${\text{dist}}^{\ast }(\mathbf{z};{\nu }_0^{\ast })$ to be a dual 0-cochain on the nodes of the dual graph ${\overline{\mathcal{K}}}^{\ast }$ which gives the shortest path distances from ${\nu }_0^{\ast }$ (node dual to outer void), to all other nodes.

  • For any two nodes ${\eta }^{\ast },{\tau }^{\ast }\in {\mathcal{F}}^{\ast }$, the dual distance cochain satisfies ${\text{dist}}_z^{\ast }({\tau }^{\ast })-{\text{dist}}_z^{\ast }({\eta }^{\ast })={\mathbf{z}}^{\ast }({\eta }^{\ast }\to {\tau }^{\ast })$.

• The max-bounding chain LP on $\overline{\mathcal{K}}$ is given below:

$$\begin{array}{rlrlr}& \underset{\overline{\pi }}{\max }& \sum _{{\mathcal{V}}_I}|\overline{\pi }({\nu }_t)-{\beta }_d\overline{\pi }({\eta }_0)|\ge 0& & \\ & \text{s.t}& \overline{\pi }(\tau )\le \mathbf{z}(\eta \uparrow \tau )+\overline{\pi }(\eta )& & \forall (\eta \uparrow \tau )\in {\mathcal{K}}_d\\ & & \overline{\pi }({\nu }_0)=0& & \\ & & \overline{\pi }\in {\mathcal{C}}^{d+1}(\overline{\mathcal{K}};\mathbb{Z})& & \end{array}$$

Question: I don’t understand how this solves the max-bounding chain problem. But honestly, I’m completely lost in all the notation at this point. Right now my understanding is that we are representing the OHCP as an OHBP due to the lemmas stating that the $d$-cycles on $\mathcal{K}$ turn into $d$-boundaries on $\overline{\mathcal{K}}$. As an optimization problem, we’d state OHBP as follows:

$$\begin{array}{rlr}& \min & |\alpha (\overline{\pi })|\\ & \text{s.t.}& \mathbf{z}-\overline{\mathbf{x}}={\partial }_{d+1}\overline{\pi }\\ & & \overline{\mathbf{x}}\in {\mathcal{Z}}_d(\overline{\mathcal{K}}),\overline{\pi }\in {\mathcal{C}}_{d+1}(\overline{\mathcal{K}})\end{array}$$

We need our solution to be a $d$-cycle in $\mathcal{K}$ (and optimal), so $\overline{\pi }(\nu )=0$ for all $\nu \notin \mathcal{K}$. Even given that $d$-cycles turn into $d$-boundaries, I do not see how optimal solution to the above (assuming it’s even a $d$-cycle) would give the solution to the OHCP.

• To optimize the flux of coflow through $\mathbf{z}$ it is sufficient that the $d$-coflow $\mathbf{f}$ is non-zero only on the non-zero homology classes of $\mathbf{z}$.

Question: Why? I assume this is will be shown later?

• Let $\mathcal{S}=\{{\nu }_s\mid {\text{dist}}_z({\nu }_s)>0\}$, $\mathcal{Q}=\{{\nu }_l\mid {\text{dist}}_z({\nu }_l)=0\}$ and $\mathcal{T}=\{{\nu }_t\mid {\text{dist}}_z({\nu }_t)<0\}$.
• Three cases:
  • $\mathcal{S}=\varnothing$ and $\mathcal{T}\ne \varnothing$: then $\mathbf{z}$ is curling in CCW. So we set $\mathcal{S}=\mathcal{Q}$ and $\mathcal{Q}=\varnothing$. Question: but $\mathcal{Q}\ne \varnothing$?
  • $\mathcal{S}\ne \varnothing$ and $\mathcal{T}=\varnothing$: then $\mathbf{z}$ is curling in CW. So we set $\mathcal{T}=\mathcal{Q}$ and $\mathcal{Q}=\varnothing$. Question: same as above.
  • $S\ne \varnothing$ and $\mathcal{T}\ne \varnothing$: then $\mathbf{z}$ is a mix of CW and CCW parts.

Comment: At this point I’ve spent almost 6 hours reading this paper (for the third time) and just now getting to the network flow model. Based purely on Figure 5, it feels like the majority of the past 14 pages of the paper were unnecessary to understand the model. Perhaps things could be shuffled around? Figure 5 should be much sooner and the other content pushed to later for the readers interested in why the model works.

I need a break and will have to return to the paper tomorrow. I’ll likely have forgotten most of it by then; especially the notation.