lemmatheorem lemma corollarytheorem corollary

# Generalized max-flows and min-cuts in simplicial complexes

William Maxwell  Amir Nayyeri

###### Abstract

We consider high dimensional variants of the maximum flow and minimum cut
problems in the setting of simplicial complexes and provide both algorithmic
and hardness results. By viewing flows and cuts topologically in terms of the
simplicial (co)boundary operator we can state these problems as linear
programs and show that they are dual to one another. Unlike graphs, complexes
with integral capacity constraints may have fractional max-flows. We show that
computing a maximum integral flow is NP-hard. Moreover, we give a
combinatorial definition of a simplicial cut that seems more natural in the
context of optimization problems and show that computing such a cut is NP-
hard. However, we provide conditions on the simplicial complex for when the
cut found by the linear program is a combinatorial cut. For $d$-dimensional
simplicial complexes embedded into $\mathbb{R}^{d+1}$ we provide algorithms
operating on the dual graph: computing a maximum flow is dual to computing a
shortest path and computing a minimum cut is dual to computing a minimum cost
circulation. Finally, we investigate the Ford-Fulkerson algorithm on
simplicial complexes, prove its correctness, and provide a heuristic which
guarantees it to halt.

##  1 Introduction

Computing flows and cuts are fundamental algorithmic problems in graphs, which
are one dimensional simplicial complexes. In this paper, we explore
generalizations of these algorithmic problems in higher dimensional simplicial
complexes. Flows and cuts in simplicial complexes have natural algebraic
definitions arising from the theory of simplicial (co)homology. A flow is an
element of the kernel of the simplicial boundary operator, and a cut is an
element of the image of the simplicial coboundary operator. These subspaces
serve as generalizations of the cycle and cut spaces of a graph. This
generalization has been studied by Duval, Klivans, and Martin in the setting
of CW complexes [9]. We formulate the algorithmic problems of computing max-
flows and min-cuts algebraically. By forgetting about the underlying graph
structure and focusing on the (co)boundary operators, we obtain methods that
naturally generalize to high dimensions.

In a graph an $st$-flow is an assignment of real values to the edges
satisfying the conservation of flow constraints: the net flow out of any
vertex other than $s$ and $t$ is zero, and, thus, the net flow that leaves $s$
is equal to the net flow that enters $t$. Therefore, each $st$-flow can be
viewed as a circulation in another graph with an extra edge that connects $t$
to $s$. Circulations are elements of the cycle space of the graph with
coefficients taken over $\mathbb{R}$. In a $d$-dimensional simplicial complex
$\mathcal{K}$ the $d$-dimensional cycles are the formal sums (over
$\mathbb{R}$) of $d$-dimensional simplices whose boundary is zero. Because
there are no $(d+1)$-simplices flows are the elements of the $d$th homology
group $H_{d}(\mathcal{K},\mathbb{R})$. The maximum flow problem in a
simplicial complex asks to find an optimal element of
$H_{d}(\mathcal{K},\mathbb{R})$ subject to capacity constraints.

The max-flow min-cut theorem states that in a graph the value of a maximum
$st$-flow is equal to the value of a minimum $st$-cut. This result is a
special case of linear programming duality. By rewriting the linear program in
terms of the (co)boundary operator we obtain a similar result for simplicial
complexes. The question of whether or not a similar max-flow min-cut theorem
holds for simplicial complexes was asked, and left open, in a paper by Latorre
[22]. We give a positive answer to this question, but with a caveat. When
viewing flows and cuts from a topological point of view their linear programs
are dual to one another. However, we also provide a combinatorial definition
of a cut which feels more natural for a minimization problem. Topological and
combinatorial cuts are equivalent for graphs, but they become different in
dimensions $d>1$. Flows in higher dimension, are dual to topological cuts, but
not combinatorial cuts in general. From a computational complexity viewpoint
the two notions of cuts are very different. We show that computing a minimum
topological cut can be solved via linear programming, but that computing a
minimum combinatorial cut is NP-hard.

A closely related problem is the problem of computing a max-flow in a graph
which admits an embedding into some topological space. The most well-studied
cases are planar graphs and the more general case when the graph embeds into a
surface [3, 4, 5, 12, 14, 15, 16, 20, 21, 24, 25]. Max-flows and min-cuts are
computationally easier to solve in surface embedded graphs, especially planar
graphs. We consider this problem generalized to simplicial complexes. Planar
graphs are 1-dimensional complexes embedded in $\mathbb{R}^{2}$, in Section 5
we consider the special case when a $d$-dimensional simplicial complex admits
an embedding into $\mathbb{R}^{d+1}$. These complexes naturally admit a dual
graph which we use to compute maximum flows and minimum cuts (both topological
and combinatorial). We show that a maximum flow in a simplicial complex can be
found by solving a shortest paths problem in its dual graph. This idea was
used by Hassin to solve the maximum flow problem in planar graphs [15].
Further, we show that finding a minimum topological cut can be done by finding
a minimum cost circulation in its dual graph. By setting the demand equal to
one in the minimum cost circulation problem we obtain an algorithm computing a
minimum combinatorial cut.

Maximum flows in graphs can be computed using the Ford-Fulkerson algorithm.
Moreover, the fact that the Ford-Fulkerson algorithm halts serves as a proof
that there exists a maximum integral flow when the graph has integral capacity
constraints. In dimensions $d>1$ the maximum flow may be fractional, even with
integral capacity constraints. The problem arises due to the existence of
torsion in simplicial complexes of dimension $d>1$. We show that despite the
maximum flow being fractional the Ford-Fulkerson algorithm halts on simplicial
complexes. However, in order for it to halt a special heuristic on picking the
high dimensional analog of an augmenting path must be implemented. Despite the
algorithm halting it could we could not prove a polynomial upper bound on the
number of iterations it takes.

##  2 Preliminaries

#### Simplicial homology

We give a brief overview of some basic concepts from simplicial (co)homology
that will be used throughout the paper. We recommend the book by Hatcher [17]
for a more complete exposition. In this paper $\mathcal{K}$ will always be a
finite oriented $d$-dimensional simplicial complex which we now define. Given
a finite set of vertices $V$ we define a $d$-dimensional simplex to be a
subset of $d+1$ vertices of $V$. $0$-simplices are vertices, $1$-simplices are
edges, $2$-simplices are triangles, and so on. We define an abstract
simplicial complex $\mathcal{K}$ to be a finite collection of simplices with
the property that it is downward closed. That is, for every
$\sigma\in\mathcal{K}$ if $\tau\subset\sigma$ then $\tau\in\mathcal{K}$. We
call the subsets of a simplex the faces of the simplex. The dimension of
$\mathcal{K}$ is dimension of its largest simplex. Further, we define an
orientation on $\mathcal{K}$ by fixing a linear ordering on the vertices in
$V$ and treating simplices as ordered sets. An oriented simplex is a
permutation of the linear ordering, and the orientation of the simplex is the
parity of the permutation. We call oriented simplices that agree with the
linear ordering positively oriented otherwise we call them negatively
oriented.

We define a $d$-chain to be a formal sum of $d$-simplices with coefficients
over $\mathbb{R}$. By $\mathcal{K}^{d}$ we denote the $d$-skeleton of
$\mathcal{K}$ which is the set of all $d$-simplices in $\mathcal{K}$ and we
denote its cardinality by $n_{d}$. Additionally, we may assign a weight
function on the $d$-skeleton of $\mathcal{K}$ denoted
$c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}$. In the context of the maximum
flow problem we will refer to the weight function as a capacity function.

Given a simplicial complex $\mathcal{K}$ we define the $d$th chain space
$C_{d}(\mathcal{K})$ to be the vector space generated by $\mathcal{K}^{d}$
with coefficients over $\mathbb{R}$. Let $\sigma=[v_{0},\dots,v_{d}]$ be a
$d$-simplex with each $v_{i}$ a vertex. We define the simplicial boundary
operator $\partial_{d}\colon C_{d+1}(\mathcal{K})\rightarrow
C_{d}(\mathcal{K})$ by

$\partial_{d}(\sigma)=\sum_{i=0}^{d}(-1)^{i}[v_{0},\dots,\hat{v_{i}},\dots,v_{d}],$

where $[v_{0},\dots,\hat{v_{i}},\dots,v_{d}]$ denotes the $(d-1)$-simplex
obtained by removing $v_{i}$ from $\sigma$. The boundary operator extends
linearly over $\mathbb{R}$ in the natural way. The boundary operator is
defined for all $0\leq k\leq d$ and we will drop the subscript denoting it
$\partial$ when the context is clear. Since we are assuming
$C_{d}(\mathcal{K})$ to be a finite dimensional vector space we can
equivalently define the boundary operator to be the $n_{d-1}\times n_{d}$
matrix such that the entry $\partial_{i,j}$ is equal to $1$ or $-1$ (depending
on the orientation) if the $i$th $(d-1)$-simplex is a face of the $j$th
$d$-simplex, and 0 otherwise. With the boundary operator we define the chain
complex on $\mathcal{K}$ to be the following sequence of vector spaces
connected by their boundary operators.

$\dots\xrightarrow{\partial_{d+1}}C_{d}(\mathcal{K})\xrightarrow{\partial_{d}}C_{d-1}(\mathcal{K})\xrightarrow{\partial_{d-1}}\dots\xrightarrow{\partial_{2}}C_{1}(\mathcal{K})\xrightarrow{\partial_{1}}C_{0}(\mathcal{K})\rightarrow
0$

The space of $d$-cycles $Z_{d}(\mathcal{K})$ is defined to be
$\ker(\partial_{d})$ and the space of $d$-boundaries $B_{d}(\mathcal{K})$ is
defined to be $\operatorname{im}(\partial_{d+1})$. We call any $d$-cycle
$\gamma\in B_{d}(\mathcal{K})$ a null-homologous cycle. Since
$\partial_{d}\circ\partial_{d+1}=0$ the quotient space
$H_{d}(\mathcal{K})=Z_{d}(\mathcal{K})/B_{d}(\mathcal{K})$ is well-defined,
and we call $H_{d}(\mathcal{K})$ the $d$th homology space of $\mathcal{K}$. By
$\beta_{d}$ we denote the $d$th Betti number of $\mathcal{K}$ which is defined
to be $\beta_{d}=\dim H_{d}(\mathcal{K})$.

We obtain the cochain space by dualizing $C_{d}(\mathcal{K})$ in the following
way. The $d$th cochain space $C^{d}(\mathcal{K})$ is defined to be the dual
space of $C_{d}(\mathcal{K})$, that is, the space of all linear functions
$f\colon C_{d}(\mathcal{K})\rightarrow\mathbb{R}$. We call $f$ a cochain and
we define the coboundary operator $\delta_{d}\colon
C^{d-1}(\mathcal{K})\rightarrow C^{d}(\mathcal{K})$ on cochains as the
composition of functions $\delta_{d}f=f\circ\partial_{d}$. The cochain complex
is the following sequence of cochain spaces.

$\dots\xleftarrow{\delta_{d+1}}C^{d}(\mathcal{K})\xleftarrow{\delta_{d}}C^{d-1}(\mathcal{K})\xleftarrow{\delta_{d-1}}\dots\xleftarrow{\delta_{2}}C^{1}(\mathcal{K})\xleftarrow{\delta_{1}}C^{0}(\mathcal{K})\leftarrow
0$

The space of $d$-cocycles $Z^{d}(\mathcal{K})$ is defined to be
$\ker(\delta_{d+1})$ and the space of $d$-coboundaries $B^{d}(\mathcal{K})$ is
defined to be $\operatorname{im}(\delta_{d})$. Again, since
$\delta_{d+1}\circ\delta_{d}=0$ the quotient space
$H^{d}(\mathcal{K})=Z^{d}(\mathcal{K})/B^{d}(\mathcal{K})$ is well-defined and
we call $H^{d}(\mathcal{K})$ the $d$th cohomology space of $\mathcal{K}$.

Since $C_{d}(\mathcal{K})$ and $C^{d}(\mathcal{K})$ are finite dimensional
vector spaces we have the isomorphisms $C_{d}(\mathcal{K})\cong
C^{d}(\mathcal{K})$ and $H_{d}(\mathcal{K})\cong H^{d}(\mathcal{K})$. It can
be shown that the coboundary operator as a matrix is equal to the transpose of
the boundary operator: $\delta_{d}=\partial_{d}^{T}$. We will view
$d$-(co)chains as both $d$-dimensional vectors and as linear functions
$C_{d}(\mathcal{K})\rightarrow\mathbb{R}$ whenever it is convenient to do so.
However, we will refer to flows as $d$-chains and cuts as $d$-cochains unless
explicitly stated otherwise. We will often want to talk about the underlying
set of simplices of the (co)chain and refer to this set as the support of the
(co)chain; the support of a chain $\sigma=\sum\alpha_{i}\sigma_{i}$ is defined
as the set
$\textsf{supp}(\sigma)=\\{\sigma_{i}\in\mathcal{K}^{d}\mid\alpha_{i}\neq
0\\}$.

We will need to define the notion of relative homology in order to cite known
results about the boundary matrix of a simplicial complex. Let
$\mathcal{K}_{0}\subseteq\mathcal{K}$ be a subcomplex of $\mathcal{K}$. We
call the quotient space
$C_{d}(\mathcal{K},\mathcal{K}_{0})=C_{d}(\mathcal{K})/C_{d}(\mathcal{K}_{0})$
the space of $d$-dimensional relative chains and there is an induced mapping
$\partial_{d}^{\mathcal{K},\mathcal{K}_{0}}\colon
C_{d}(\mathcal{K},\mathcal{K}_{0})\rightarrow
C_{d-1}(\mathcal{K},\mathcal{K}_{0})$. From the induced mapping we define the
spaces of relative $d$-cycles $Z_{d}(\mathcal{K},\mathcal{K}_{0})$, relative
$d$-boundaries $B_{d}(\mathcal{K},\mathcal{K}_{0})$, and relative
$d$-dimensional homology $H_{d}(\mathcal{K},\mathcal{K}_{0})$ in the natural
way. Further, let $\mathcal{L}\subseteq\mathcal{K}$ be a pure $d$-dimensional
subcomplex; that is, every $(d-1)$-simplex in $\mathcal{L}$ is incident to
some $d$-simplex in $\mathcal{L}$. Let $\mathcal{L}_{0}\subseteq\mathcal{L}$
be a pure $(d-1)$-dimensional subcomplex of $\mathcal{L}$. The induced map on
relative homology $\partial_{d}^{\mathcal{L},\mathcal{L}_{0}}\colon
C_{d}(\mathcal{L},\mathcal{L}_{0})\rightarrow
C_{d-1}(\mathcal{L},\mathcal{L}_{0})$ has a natural matrix representation. We
construct the matrix $\partial_{d}^{\mathcal{L},\mathcal{L}_{0}}$ by starting
with $\partial_{d}$ and including the columns corresponding to $d$-simplices
in $\mathcal{L}$ while excluding the rows corresponding to $(d-1)$-simplices
in $\mathcal{L}_{0}$.

#### Dual graphs

We will provide algorithms for a special class of simplicial complexes:
embedded complexes. This class of simplicial complexes admits a natural graph
structure known as the dual graph. Let $\mathcal{K}$ be a $d$-dimensional
simplicial complex. We say $\mathcal{K}$ has an embedding into
$\mathbb{R}^{d+1}$ if there exists a function
$f\colon\mathcal{K}\rightarrow\mathbb{R}$ such that $f$ restricted to any
$k$-simplex is an injection into a subspace homeomorphic to a $k$-dimensional
disk. Moreover, for any two simplices $\sigma,\tau\in\mathcal{K}$ we require
that $f(\sigma)\cap f(\tau)=f(\sigma\cap\tau)$. That is, the image of any two
simplices only intersects at their shared faces.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex embedded in
$\mathbb{R}^{d+1}$. The Alexander duality theorem implies that
$\mathbb{R}^{d+1}\setminus\mathcal{K}$ consists of $\dim H_{d}(\mathcal{K})+1$
connected components [2], see [17, Corollary 3.45] for a modern treatment. We
define the dual graph $\mathcal{K}^{*}$ of $\mathcal{K}$ to be the graph whose
vertices are in bijection with the connected components of
$\mathbb{R}^{d+1}\setminus\mathcal{K}$ and whose edges are in bijection with
the $d$-simplices of $\mathcal{K}$. Since simplices are two-sided each
$d$-simplex is on the boundary of at most two connected components of
$\mathbb{R}^{d+1}\setminus\mathcal{K}$, and the endpoints of its dual edge are
dual to these connected components. Exactly one connected component of
$\mathbb{R}^{d+1}\setminus\mathcal{K}$ is unbounded and we denote the vertex
dual to this component by $v_{\infty}$.

#### Integral coefficients

In order to state our results regarding integral solutions we will need to
define the integral homology groups of a simplicial complex. Given a
simplicial complex $\mathcal{K}$ we define
$C_{d}(\mathcal{K},\mathbb{Z}),Z_{d}(\mathcal{K},\mathbb{Z}),B_{d}(\mathcal{K},\mathbb{Z}),$
and $H_{d}(\mathcal{K},\mathbb{Z})$ in the same was as before, but with
coefficients over $\mathbb{Z}$ instead of $\mathbb{R}$. With this change we no
longer have vector spaces, but instead have free abelian groups. The
fundamental theorem of finitely generated abelian groups gives us the
decomposition
$H_{d}(\mathcal{K},\mathbb{Z})\cong\mathbb{Z}^{k}\oplus\mathbb{Z}_{t_{1}}\oplus\dots\oplus\mathbb{Z}_{t_{n}}$
for some $k\in\mathbb{N}$. We call the subgroup
$\mathbb{Z}_{t_{1}}\oplus\dots\oplus\mathbb{Z}_{t_{n}}$ the torsion subgroup
of $H_{d}(\mathcal{K},\mathbb{Z})$ and when this subgroup is trivial we call
the complex torsion-free. We say $\mathcal{K}$ is relatively torsion-free in
dimension $d$ if $H_{d}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})$ is torsion-
free for all subcomplexes $\mathcal{L}$ and $\mathcal{L}_{0}$. There exist
complexes that are torsion-free but are not relatively torsion-free; see [7]
for examples.

#### Total unimodularity

Let $A$ be a matrix; we say that $A$ is totally unimodular if every square
submatrix $A^{\prime}$ of $A$ has $\det(A^{\prime})\in\\{-1,0,1\\}$. Totally
unimodular matrices are important in combinatorial optimization because linear
programs with totally unimodular constraint matrices are guaranteed to have
integral solutions [13]. Dey, Hirani, and Krishnamoorthy have provided
topological conditions on when a simplicial complex has a totally unimodular
boundary matrix [7] stated below. We call a simplicial complex meeting the
criteria of Theorem 2.1 relative torsion-free in dimension $d-1$.

######  Theorem 2.1 (Dey et al. [7], Theorem 5.2).

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex. The boundary matrix
$\partial\colon C_{d}(\mathcal{K})\rightarrow C_{d-1}(\mathcal{K})$ is totally
unimodular if and only if $H_{d-1}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})$ is
torsion-free for all pure subcomplexes $\mathcal{L}_{0},\mathcal{L}$ of
$\mathcal{K}$ of dimensions $d-1$ and $d$ where
$\mathcal{L}_{0}\subset\mathcal{L}$.

#### Hodge theory

Throughout this paper we utilize discrete Hodge theory and recommend the
survey by Lim [23] as an introduction to the topic. In particular, we use the
Hodge decomposition which can be stated as a result on real valued matrices
satisfying $AB=0$.

######  Theorem 2.2 (Hodge decomposition [23]).

Let $A\in\mathbb{R}^{m\times n}$ and $B\in\mathbb{R}^{n\times p}$ be matrices
satisfying $AB=0$. We can decompose $\mathbb{R}^{n}$ into the orthogonal
direct sum,

$\mathbb{R}^{n}=\operatorname{im}(A^{T})\oplus\ker(A^{T}A+BB^{T})\oplus\operatorname{im}(B).$

Setting $A=\partial_{d}$ and $B=\partial_{d+1}$ yields the Hodge decomposition
for simplicial complexes. The middle term of the direct sum becomes
$\ker(\delta_{d+1}\partial_{d+1}+\partial_{d}\delta_{d})$. The linear operator
$\delta_{d+1}\partial_{d+1}+\partial_{d}\delta_{d}$ is known as the
combinatorial Laplacian of $\mathcal{K}$ which is a generalization of the
graph Laplacian. Moreover, it can be shown that
$\ker(\delta_{d+1}\partial_{d+1}+\partial_{d}\delta_{d})\cong
H_{d}(\mathcal{K},\mathbb{R})$. We now state the Hodge decomposition on
simplicial complexes as the following isomorphism:

$C_{d}(\mathcal{K},\mathbb{R})\cong\operatorname{im}(\delta_{d})\oplus
H_{d}(\mathcal{K},\mathbb{R})\oplus\operatorname{im}(\partial_{d+1}).$

##  3 Flows and cuts

In this section we give an overview of our generalizations of flows and cuts
from graphs to simplicial complexes. Flows and cuts in higher dimensional
settings have been studied previously. Duval, Klivans, and Martin have
generalized cuts and flows to the setting of CW complexes [9]. Their
definitions are algebraic; defining cuts to be elements of
$\operatorname{im}(\delta)$ and flows to be elements of $\ker(\partial)$. Our
definitions are closely related, but are motivated by the algorithmic problems
of computing maximum flows and minimum cuts. In Section 3.1 we give
definitions of flows and cuts from from the perspective of algebraic topology,
and in Section 3.2 we give a combinatorial definition of a cut in a simplicial
complex. The distinction between the two types of cuts will be important when
formulating the minimum cut problem on simplicial complexes.

###  3.1 Topological flows and cuts

First we briefly recall the definition of an $st$-flow in a directed graph
$G=(V,E)$. An $st$-flow $f$ is a function $f\colon E\rightarrow\mathbb{R}$
satisfying the conservation of flow constraint: for all $v\in
V\setminus\\{s,t\\}$ we have $\sum_{(u,v)\in E}f(u,v)=\sum_{(v,u)\in
E}f(v,u)$. That is, the amount of flow entering the vertex equals the amount
of flow leaving the vertex. The value of $f$ is equal to the amount of flow
leaving $s$ (or equivalently, entering $t$). Alternatively, we may view $f$ as
a 1-chain and we have $\partial f=k(t-s)$ where $k$ is the value of $f$. Note
that $t-s$ is a null-homologous 0-cycle. More generally, for any null-
homologous $(d-1)$-cycle $\gamma$ we call a $d$-chain $f$ with $\partial
f=k\gamma$ a $\gamma$-flow of value $k$. Note that under our naming convention
an $st$-flow in a graph would be called a $(t-s)$-flow. However, in the case
of graphs we use the traditional naming convention and call a flow from $s$ to
$t$ an $st$-flow.

######  Definition 1 ($\gamma$-flow).

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex and $\gamma$ be a
null-homologous $(d-1)$-cycle in $\mathcal{K}$. A $\gamma$-flow is a $d$-chain
$f$ with $\partial f=k\gamma$ where $k\in\mathbb{R}$. We call $k$ the value of
the flow $f$ and denote the value of $f$ by $\|f\|$. We say that $f$ is
feasible with respect to a capacity function
$c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}^{+}$ if $0\leq f(\sigma)\leq
c(\sigma)$ for all $\sigma\in\mathcal{K}^{d}$.

Our definition of a $\gamma$-flow is very close to the algebraic definition
which is element of $\ker(\partial)$. Given a simplicial complex $\mathcal{K}$
and a $\gamma$-flow $f$ of value $k$ we convert $f$ into a circulation, where
a circulation is defined to be an element of $\ker(\partial)$. To convert $f$
into a circulation we add an additional basis element to $C_{d}(\mathcal{K})$,
call it $\Sigma$, whose boundary is $\partial\Sigma=-\gamma$. This operation
is purely algebraic; we should think of it as operating on the chain complex
rather than the underlying topological space. Now we construct the circulation
$f^{\prime}=f+k\Sigma$. We call any circulation built from a $\gamma$-flow a
$\gamma$-circulation. Clearly, $f^{\prime}\in\ker(\partial)$ in the new chain
complex. Moreover, there is a clear bijection between $\gamma$-flows and
$\gamma$-circulations. The value of the circulation is the value of
$f^{\prime}(\Sigma)$, so this bijection preserves the value.

We now shift our focus to the generalization of cuts to a simplicial complex.
The algebraic definition, elements of $\operatorname{im}(\delta)$, is natural.
The cut space of a graph is commonly defined to be the space spanned by the
coboundaries of each vertex. In a simplicial complex $\mathcal{K}$, removing
the support of a $d$-chain in $\operatorname{im}(\delta)$ increases $\dim
H_{d-1}(\mathcal{K})$. In a graph $G$, removing the support of any 1-chain in
$\operatorname{im}(\delta)$ increases $\dim H_{0}(G)$ which is equivalent to
increasing the number of connected components of $G$.

The above definition implies that a cut is a $d$-chain in a $d$-dimensional
simplicial complex. However, for our purposes we will define a cut to be a
$(d-1)$-cochain. To motivate our definition we recall the notion of an
$st$-cut in a graph. An $st$-cut in a graph is a partition of the vertices
into sets $S$ and $T$ such that $s\in S$ and $t\in T$. Define $p\colon
V(G)\rightarrow\\{0,1\\}$ such that $p(v)=1$ if $v\in S$ and $p(v)=0$ if $v\in
T$. The support of the coboundary of $p$ is a set of edges whose removal
destroys all $st$-paths. That is, upon removing the support, the 0-cycle $t-s$
is no longer null-homologous. Moreover, $p$ is a $0$-cochain with $p(t-s)=-1$.
The sign of $p(t-s)$ will be important when we consider directed cuts. With
this in mind we define our notion of a $\gamma$-cut.

######  Definition 2 ($\gamma$-cut).

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex with weight function
$c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}^{+}$ and $\gamma$ be a null-
homologous $(d-1)$-cycle in $\mathcal{K}$. A $\gamma$-cut is a $(d-1)$-cochain
$p$ such that $p(\gamma)=-1$. Denote the coboundary of $p$ as the formal sum
$\delta(p)=\sum\alpha_{i}\sigma_{i}$, we define the size of a $\gamma$-cut to
be $\|p\|=\sum|\alpha_{i}c(\sigma_{i})|$.

Because of the requirement that $p(\gamma)=-1$ we call $p$ a unit
$\gamma$-cut. By relaxing this requirement to $p(\gamma)<0$ the cochain $p$
still behaves as a $\gamma$-cut, but its size can become arbitrarily small by
multiplying by some small value $\epsilon>0$. We justify our definition with
the following proposition which shows that removing the support of the
coboundary of a $\gamma$-cut prevents $\gamma$ from being null-homologous.

######  Proposition 3.1.

Let $\mathcal{K}$ be $d$-dimensional simplicial complex and $p$ be a
$\gamma$-cut. The cycle $\gamma$ is not null-homologous in the subcomplex
$\mathcal{K}\setminus\textsf{supp}(\delta(p))$.

###### Proof.

By way of contradiction let $\Gamma$ be a $d$-chain in
$\mathcal{K}\setminus\textsf{supp}(\delta(p))$ such that
$\partial\Gamma=\gamma$. Since $\delta(p)=0$ in
$\mathcal{K}\setminus\textsf{supp}(\delta(p))$, we have that
$\langle\Gamma,\delta(p)\rangle=0$ in
$\mathcal{K}\setminus\textsf{supp}(\delta(p))$. However, this implies that
$0=\langle\Gamma,\delta(p)\rangle=\langle\partial\Gamma,p\rangle=\langle\gamma,p\rangle=p(\gamma)=0$,
a contradiction as $p$ is a $\gamma$-cut and $p(\gamma)=-1$. ∎

###  3.2 Combinatorial cuts

Alternatively, we can view a $\gamma$-cut as a discrete set of $d$-simplices
rather than a $d$-chain. In the case of graphs a combinatorial $st$-cut is
just a set of edges whose removal disconnects $s$ from $t$. This distinction
will become important when we consider the minimization problem of finding a
minimum cost set of $d$-simplices whose removal prevents $\gamma$ from being
null-homologous.

######  Definition 3 (Combinatorial $\gamma$-cut).

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex with weight function
$c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}^{+}$ and $\gamma$ be a null-
homologous $(d-1)$-cycle in $\mathcal{K}$. A combinatorial $\gamma$-cut is a
set of $d$-simplices $C\subseteq\mathcal{K}^{d}$ such that $\gamma$ is not
null-homologous in $\mathcal{K}\setminus\textsf{supp}(C)$. The size of a
combinatorial $\gamma$-cut is defined by the sum of the weights of the
$d$-simplices $\|C\|=\sum_{\sigma\in C}c(\sigma)$.

The next proposition shows a relationship between $\gamma$-cuts and
combinatorial $\gamma$-cuts. Removing a combinatorial $\gamma$-cut $C$ from
$\mathcal{K}$ increases $\dim H_{d-1}(\mathcal{K})$. This is because removing
$C$ must decrease the rank of $\partial_{d}$ and by duality this also
decreases the rank of $\delta_{d}$ which increases the dimension of
$H^{d-1}(\mathcal{K})\cong H_{d-1}(\mathcal{K})$. It follows that $C$ must
contain the support of some coboundary. Given an additional minimality
condition on $C$ we show that $C$ is equal to the support of some coboundary.

######  Proposition 3.2.

Let $C$ be a combinatorial $\gamma$-cut in a $d$-dimensional simplicial
complex $\mathcal{K}$. Further, assume that $C$ is minimal in the sense that
for all $C^{\prime}\subset C$ we have $\dim H_{d-1}(\mathcal{K}\setminus
C^{\prime})<\dim H_{d-1}(\mathcal{K}\setminus C)$. There exists a
$(d-1)$-cochain $p$ such that $\textsf{supp}(\delta(p))=C$.

###### Proof.

Recall that
$H_{d-1}(\mathcal{K})=\ker(\partial_{d-1})/\operatorname{im}(\partial_{d})$,
$H^{d-1}=\ker(\delta_{d})/\operatorname{im}(\delta_{d-1})$, and over real
coefficients we have the isomorphism $H_{d-1}(\mathcal{K})\cong
H^{d-1}(\mathcal{K})$. Removing the set of $d$-simplices $C$ from
$\mathcal{K}$ does not affect $\ker(\partial_{d-1})$ or
$\operatorname{im}(\delta_{d-1})$. However, as $C$ is a combinatorial
$\gamma$-cut it must decrease the dimension of
$\operatorname{im}(\partial_{d})$ and increase the dimension of
$\ker(\delta_{d})$. It follows that there must exist some $(d-1)$-cochain $p$
such that $\delta_{d}(p)\neq 0$ in $\mathcal{K}$ but $\delta_{d}(p)=0$ in
$\mathcal{K}\setminus C$. Hence, $\textsf{supp}(\delta_{d}(p))\subseteq C$.
Without loss of generality we choose $p$ such that
$|\textsf{supp}(\delta_{d}(p))|$ is maximized. Define $C^{\prime}\coloneqq
C\setminus|\textsf{supp}(\delta_{d}(p))|$. By minimality we have $\dim
H_{d-1}(\mathcal{K}\setminus C^{\prime})<\dim H_{d-1}(\mathcal{K}\setminus
C)$, so there is some $(d-1)$-cycle $\gamma^{\prime}$ that is null-homologous
in $\mathcal{K}\setminus C^{\prime}$ but not null-homologous in
$\mathcal{K}\setminus C$. Dually, there is some $(d-1)$-cochain $p^{\prime}$
with $\delta_{d}(p^{\prime})\neq 0$ in $\mathcal{K}\setminus C^{\prime}$ but
$\delta_{p}(p^{\prime})=0$ in $\mathcal{K}\setminus C$. It follows that
$\delta_{d}(p+p^{\prime})=0$ in $\mathcal{K}\setminus C$ but
$\delta_{d}(p+p^{\prime})\neq 0$ in $\mathcal{K}$, so
$\textsf{supp}(p+p^{\prime})\subseteq C$. Since $\textsf{supp}(p)$ and
$\textsf{supp}(p^{\prime})$ are disjoint we have
$|\textsf{supp}(p)|<|\textsf{supp}(p+p^{\prime})|$, contradicting our
assumption that $p$ maximizes $|\textsf{supp}(p)|$. ∎

In graphs the linear program solving the minimum $st$-cut problem takes as
input a directed graph and returns a set of directed edges whose removal
destroys all directed $st$-paths. This is called a directed cut. After
removing the directed cut the 0-cycle $t-s$ may still be null-homologous; we
can find a 1-chain with boundary $t-s$ using negative coefficients to traverse
an edge in the backwards direction. In order to generalize the minimum cut
linear program to simplicial complexes we will need to define a directed
combinatorial $\gamma$-cut, which requires the additional assumption that the
$d$-simplices of $\mathcal{K}$ are oriented.

######  Definition 4 (Directed combinatorial $\gamma$-cut).

Let $\mathcal{K}$ be an oriented $d$-dimensional simplicial complex with
weight function $c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}$ and $\gamma$ be
a null-homologous $(d-1)$-cycle in $\mathcal{K}$. A directed combinatorial
$\gamma$-cut is a set of $d$-simplices $C\subset\mathcal{K}^{d}$ such that in
$\mathcal{K}\setminus\textsf{supp}(C)$ there exists no $d$-chain $\Gamma$ with
non-negative coefficients such that $\partial\Gamma=\gamma$. The size of a
directed combinatorial $\gamma$-cut is defined by the sum of the weights of
the $d$-simplices $\|C\|=\sum_{\sigma\in C}c(\sigma)$.

Given a directed graph consider an $st$-cut given by the cochain definition.
That is, a 0-cochain $p\colon V(G)\rightarrow\\{0,1\\}$ with $p(s)=1$ and
$p(t)=0$ partitioning $V$ into $S$ and $T$. The support of $\delta(p)$
consists of two types of edges: edges leaving $S$ and entering $T$, and edges
leaving $T$ and entering $S$. If $e\in E$ leaves $S$ and enters $T$ we have
$(p\circ\partial)(e)=-1$ and if $e$ leaves $T$ and enters $S$ we have
$(p\circ\partial)(e)=1$. To construct a directed $st$-cut we simply take all
of the edges mapped to $-1$. The following proposition shows that we can build
a directed combinatorial $\gamma$-cut from a coboundary just like in the case
of directed graphs.

######  Proposition 3.3.

Let $p$ be a $\gamma$-cut with coboundary
$\delta(p)=\sum\alpha_{i}\sigma_{i}$. The set of $d$-simplices
$C=\\{\sigma_{i}\mid\alpha_{i}<0\\}$ is a directed combinatorial $\gamma$-cut.

###### Proof.

By way of contradiction let $\Gamma$ be a non-negative $d$-chain in
$\mathcal{K}\setminus C$ with $\partial\Gamma=\gamma$. By the definition of
$C$ we have $\langle\Gamma,\delta(p)\rangle\geq 0$ in $\mathcal{K}\setminus
C$. Construct a new chain complex by adding an additional basis element
$\Sigma$ to $C_{d}(\mathcal{K})$ such that $\partial\Sigma=-\gamma$. By
construction $\langle\Sigma,\delta(p)\rangle=-p(\gamma)=1$, hence we have
$\langle\Gamma+\Sigma,\delta(p)\rangle>0$. However, $\Gamma+\Sigma$ is a
$d$-cycle and $\delta(p)$ is a $d$-coboundary, so the Hodge decomposition
ensures that they are orthogonal. Hence,
$\langle\Gamma+\Sigma,\delta(p)\rangle=0$, a contradiction. ∎

To conclude the section we will show that computing a minimum combinatorial
$\gamma$-cut is NP-hard. As we will see in Section 4 minimum topological
$\gamma$-cuts can be computed with linear programming. Our hardness result
holds for both the directed and undirected cases. Our hardness result is a
reduction from the well-known NP-hard hitting set problem which we will now
define. Given a set $S$ and a collection of subsets
$\Sigma=(S_{1},\dots,S_{n})$ where $S_{i}\subseteq S$ the hitting set problem
asks to find the smallest subset $S^{\prime}\subseteq S$ such that
$S^{\prime}\cap S_{i}\neq\emptyset$ for all $S_{i}$. We call such a subset
$S^{\prime}$ a hitting set for $(S,\Sigma)$.

######  Theorem 3.1.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex and $\gamma$ be a
null-homologous $(d-1)$-cycle. Computing a minimum combinatorial $\gamma$-cut
is NP-hard for $d\geq 2$.

###### Proof.

Our proof is a reduction from the hitting set problem. First we consider the
case when $d=2$ then we generalize to any $d\geq 2$. Let $S$ be a set and
$\Sigma=(S_{1},\dots,S_{n})$ where each $S_{i}\subseteq S$. We construct a
$2$-dimensional simplicial complex $\mathcal{K}$ from $S$ and $\Sigma$ in the
following way. For each $S_{i}\in\Sigma$ construct a triangulated disk
$\mathcal{D}_{i}$ such that $\partial\mathcal{D}_{i}=\gamma$. That is, each
$\mathcal{D}_{i}$ shares the common boundary $\gamma$. To accomplish this we
construct each $\mathcal{D}_{i}$ by beginning with a single triangle $t$ with
$\partial t=\gamma$ and repeatedly adding a new vertex in the center of some
triangle with edges connecting it to every vertex in that triangle. By this
process we can construct a disk containing any odd number of triangles as each
step increments the number of triangles in the disk by two. Moreover, at each
step the boundary of the disk is always $\gamma$. We construct each disk
$\mathcal{D}_{i}$ such that $\mathcal{D}_{i}$ consists of one triangle
$t_{i,s}$ for each element $s\in S_{i}$ and potentially one extra triangle
$t^{\prime}_{i}$ in the case that $|S_{i}|$ is even. Next, for each $s\in S$
and $S_{i}$ with $s\in S_{i}$, we construct the quotient space by identifying
each $t_{i,s}$ into a single triangle. A minimum combinatorial $\gamma$-cut
$C$ must contain at least one triangle from each $\mathcal{D}_{i}$ and without
loss of generality we can assume $C$ does not contain any $t^{\prime}_{i}$. If
$t_{i}^{\prime}\in C$ then by minimality it is the only triangle in
$C\cap\textsf{supp}(\mathcal{D}_{i})$ and we can swap it with any other
triangle in $\mathcal{D}_{i}$ without increasing the size of the cut. By
construction $C$ is a hitting set for $(S,\Sigma)$ since each
$C\cap\textsf{supp}(\mathcal{D}_{i})\neq\emptyset$ for all $\mathcal{D}_{i}$.

To perform the above construction in higher dimensions we simply start with a
single $d$-simplex $\sigma=[v_{1},\dots,v_{d+1}]$ with boundary
$\partial\sigma=\gamma$. We subdivide $\sigma$ in the following way: add an
additional vertex $v_{d+2}$ and replace $\sigma$ with the $d$-simplices
$\sigma_{i}:=[v_{1},\dots,v_{i-1},v_{d+2},v_{i+1},\dots,v_{d+1}]$ for each
$1\leq i\leq d+1$. At each step we increase the number of $d$-simplices by
$d$; moreover, at each step the complex remains homeomorphic to a
$d$-dimensional disk. Our final complex will have at most $d$ extra
$d$-simplices so for any fixed dimension $d$ the size of the complex is within
a constant factor of the size of the given hitting set instance. It remains to
show that the subdivision process does not change the boundary of the disk. To
accomplish this we will show that
$\partial\sigma=\sum_{i=1}^{d+1}\partial\sigma_{i}$.

For each $\sigma_{i}$ the boundary $\partial\sigma_{i}$ has $d$ terms in its
sum; each term is a $(d-1)$-simplex which consists of $d$ vertices. Consider
the matrix $A$ such that the entry $A_{i,j}$ contains the $j$th term of
$\partial\sigma_{i}$. Note that no term in the $j$th column will contain the
vertex $v_{j}$. Also note that the sum of the diagonal of $A$ is equal to
$\partial\sigma$. Below is an example for $d=3$.

$\begin{bmatrix}v_{2}v_{3}v_{4}&-v_{5}v_{3}v_{4}&v_{5}v_{2}v_{4}&-v_{5}v_{2}v_{3}\\\
v_{5}v_{3}v_{4}&-v_{1}v_{3}v_{4}&v_{1}v_{5}v_{4}&-v_{1}v_{5}v_{3}\\\
v_{2}v_{5}v_{4}&-v_{1}v_{5}v_{4}&v_{1}v_{2}v_{4}&-v_{1}v_{2}v_{5}\\\
v_{2}v_{3}v_{5}&-v_{1}v_{3}v_{5}&v_{1}v_{2}v_{5}&-v_{1}v_{2}v_{3}\end{bmatrix}$

The matrix $A$ is almost symmetric. The entries $A_{i,j}$ and $A_{j,i}$
contain the same vertices but possibly differ up to a sign or a permutation of
the vertices. We want to show that $A_{i,j}=-A_{j,i}$ so that the sum
$\sum_{i=1}^{d+1}\partial\sigma_{i}$ only contains diagonal which is equal to
$\partial\sigma$. The ordering of vertices in $A_{i,j}$ differs from $A_{j,i}$
by the placement of $v_{d+2}$, which we now characterize. Let $v_{i,j}$ denote
the vertex in $\sigma_{i}$ that is not included in the term $A_{i,j}$. Without
loss of generality assume $A_{i,j}$ is in the upper triangle. Then $v_{d+2}$
is in the $i$th position of $A_{i,j}$ because $v_{i,j}$ appears after it in
the ordering of $\sigma_{i}$. It follows that $v_{d+2}$ is in the $(j-1)$th in
the term $A_{j,i}$ since $v_{j,i}$ must appear before $v_{d+2}$ in the
ordering of $\sigma_{j}$. So, the position of $v_{d+2}$ in $A_{i,j}$ and
$A_{j,i}$ differs by $|i-j+1|$ and this is the number of transpositions needed
to permute $A_{i,j}$ into $A_{j,i}$. When $i\equiv j\mod 2$ the terms
$A_{i,j}$ and $A_{j,i}$ have the same sign, but differ by an odd permutation
so $A_{i,j}=-A_{j,i}$. Similarly, when $i\not\equiv j\mod 2$ the terms
$A_{i,j}$ and $A_{j,i}$ have opposite signs, but differ by an even permutation
so $A_{i,j}=-A_{j,i}$ which concludes the proof. ∎

##  4 Linear programming

###  4.1 Max-flow min-cut

A _simplicial flow network_ is a tuple $(\mathcal{K},c,\gamma)$ where
$\mathcal{K}$ is an oriented $d$-dimensional simplicial complex, $c$ is the
_capacity function_ which is a non-negative function
$c\colon\mathcal{K}^{d}\rightarrow\mathbb{R}^{\geq 0}$, and $\gamma$ is a
null-homologous $(d-1)$-cycle. In a simplicial flow network we work with real
coefficients; that is, we consider the chain groups
$C_{k}(\mathcal{K},\mathbb{R})$. In order to utilize the Hodge decomposition
(Theorem 2.2) we modify $C_{d}(\mathcal{K})$ by adding an additional basis
element $\Sigma$ such that $\partial\Sigma=-\gamma$. Moreover, we extend the
capacity function such that $c(\Sigma)=\infty$. This allows us to work with
circulations instead of flows while leaving the solution unchanged. The
notation $n_{d}$ will refer to the number of basis elements in
$C_{d}(\mathcal{K},\mathbb{R})$ which is now one more than the number of
$d$-simplices in the underlying simplicial complex.

The goal of the maximum flow problem is to find a $d$-chain $f$ obeying the
capacity constraints such that $\partial f=k\gamma$ where $k\in\mathbb{R}$ is
maximized. Equivalently, we find a $d$-cycle $f$ which maximizes $f(\Sigma)$.
The linear program for the max-flow problem in a simplicial flow network is
identical to the familiar linear program for graphs, but expressed in terms of
the coboundary operator. In a graph, conservation of flow at a vertex $v$ is
the constraint $\delta_{1}(v)\cdot f=0$; to formulate the linear program in
higher dimensions we simply replace vertices with $(d-1)$-simplices. The Hodge
decomposition states that cycles are orthogonal to coboundaries, so
conservation of flow ensures that $f$ is indeed a cycle. We now state the
linear program for max-flow in a simplicial flow network.

maximize $\displaystyle\quad f(\Sigma)$ (LP1) subject to
$\displaystyle\quad\delta(\tau)\cdot f=0$ for each $\tau\in\mathcal{K}^{d-1}$
$\displaystyle\quad 0\leq f(\sigma)\leq c(\sigma)$ for each
$\sigma\in\mathcal{K}^{d}$

We dualize LP1 to obtain a generalization of the minimum cut problem in
directed graphs. To make the dualization more explicit we will write out LP1
in matrix form: maximize $s\cdot f$ subject to $Af\leq b$ and $f\geq 0$, where
we have

$A=\begin{bmatrix}\partial\\\ -\partial\\\
I_{n_{d}}\end{bmatrix},\,b=\begin{bmatrix}0_{n_{d-1}}\\\ 0_{n_{d-1}}\\\
c\end{bmatrix},\,s=\begin{bmatrix}0_{n_{d}-1}\\\ 1\end{bmatrix}.$

The matrix $A$ has dimension $(2n_{d-1}+n_{d})\times n_{d}$. In our notation
$I_{k}$ is the $k\times k$ identity matrix and $0_{k}$ is the $k\times 1$
column vector consisting of all zeros. Since the value of the flow is equal to
$f(\Sigma)$ the vector $s$ is all zeros except for the final entry which is
indexed by $\Sigma$ and receives an entry equal to one. Further, $c$ is the
$n_{d}\times 1$ capacity vector indexed by the $d$-simplices such that the
entry indexed by $\sigma$ has value equal to $c(\sigma)$.

We can now state the dual program in matrix form: minimize $y\cdot b$ subject
to $y^{T}A\geq s$ and $y\geq 0$. The vector $y$ is a $(2n_{d-1}+n_{d})\times
1$ column vector indexed by both the $(d-1)$-simplices and the $d$-simplices.
However, only the entries indexed by $d$-simplices contribute to the objective
function since $b$ is zero everywhere outside of the capacity constraints. We
will denote the truncated vector consisting of entries indexed by
$d$-simplices by $y_{d}$ and the entry corresponding to the $d$-simplex
$\sigma\in\mathcal{K}^{d}$ will be denoted by $y_{d}(\sigma)$. Similarly we
have two truncated vectors $y^{1}_{d-1}$ and $y^{2}_{d-1}$ corresponding to
the entries indexed by the $(d-1)$-simplices. Moreover, the rows of
$y^{T}A\geq s$ are in the form

$(y_{d-1}^{1}-y_{d-1}^{2})^{T}\partial+y_{d}\geq s.$

For simplicity we define $y_{d-1}=y_{d-1}^{1}-y_{d-1}^{2}$ and write
$y_{d-1}(\tau)$ for the entry indexed by the $(d-1)$-simplex $\tau$. Putting
this together, we state the dual linear program as follows.

minimize
$\displaystyle\quad\sum_{\sigma\in\mathcal{K}^{d}}y_{d}(\sigma)c(\sigma)$
(LP2) subject to $\displaystyle\quad
y_{d-1}\cdot\partial\sigma+y_{d}(\sigma)\geq 0$ for each
$\sigma\in\mathcal{K}^{d}$ $\displaystyle\quad
y_{d-1}\cdot\partial\Sigma+y_{d}(\Sigma)=1$ $\displaystyle\quad y_{d}\geq 0$

Note the strict equality in the second constraint does not follow from the
duality. However, we can assume a strict equality since if
$y_{d-1}\cdot\partial\Sigma+y_{d}(\Sigma)>1$ we can multiply
$[y_{d-1},y_{d}]^{T}$ by some scalar $\epsilon<1$ to make the inequality
tight. This multiplication only decreases the value of $\sum
y_{d}(\sigma)c(\sigma)$ so it does not change the optimal solution.

In the case of graphs LP2 has dual variables for vertices and edges. Moreover,
there exists an integral solution such that each vertex is either assigned a 0
or a 1 since a graph cut is a partition of the vertices. The second inequality
requires $y_{0}(s)=1$ and $y_{0}(t)=0$. To see this, when solving an $st$-cut
on a graph, the basis element $\Sigma$ is an edge with $\partial\Sigma=s-t$,
and $y_{1}(\Sigma)=0$ otherwise the solution is infinite. This naturally
defines a partition of the vertices: $S$ containing vertices assigned a 1, and
$T$ containing vertices assigned a 0. The constraints force an edge to be
assigned a 1 if it leaves $S$ and enters $T$, otherwise it is assigned a 0.
This solution can be interpreted as a 0-cochain $p$ with $p(st)=1$, or in the
notation of our definition of a simplicial cut: $p(t-s)=-1$. Further,
$y_{1}(e)=1$ for every edge $e$ that is negative on $\delta(p)$ and a 0
otherwise, hence $y_{1}$ fits our definition of a directed $st$-cut in a
1-complex. We will show the same result holds in higher dimensions; that is,
$y_{d}$ is a directed $\gamma$-cut arising from the $(d-1)$-cochain $y_{d-1}$.

######  Lemma .

Let $y=[y_{d-1},y_{d}]^{T}$ be an optimal solution to LP2. The set
$\textsf{supp}(y_{d})$ is a directed combinatorial $\gamma$-cut.

###### Proof.

Note that $y_{d-1}$ can be interpreted as a $(d-1)$-cochain. Since
$c(\Sigma)=\infty$ we have $y_{d}(\Sigma)=0$, otherwise the solution is
infinite. It follows from the second constraint that
$-y_{d-1}(\gamma)=y_{d-1}(-\gamma)=y_{d-1}\cdot\partial\Sigma=1$, hence
$y_{d-1}(\gamma)=-1$ making $y_{d-1}$ a $\gamma$-cut. Expanding
$\delta(y_{d-1})$ into a linear combination of $d$-simplices
$\sum\alpha_{i}\sigma_{i}$ and applying the first inequality constraint gives
us the set equality $\textsf{supp}(y_{d})=\\{\sigma_{i}\mid\alpha_{i}<0\\}$
since $y_{d}(\sigma_{i})=0$ precisely when $\alpha_{i}>0$. Thus, the result
follows from Proposition 3.3. ∎

######  Lemma .

Let $p$ be a $\gamma$-cut with coboundary $\delta(p)=\sum\alpha_{i}\sigma_{i}$
and let $\delta(p)^{-}=\sum_{\alpha_{i}<0}\alpha_{i}\sigma_{i}$. The vector
$[p,-\delta(p)^{-}]^{T}$ is a finite feasible solution to LP2.

###### Proof.

We view the (co)chains $p$ and $-\delta(p)^{-}$ as vectors and let them take
the roles of $y_{d-1}$ and $y_{d}$, respectively. The first constraint is
satisfied since for all $\sigma\in\mathcal{K}^{d}$ we have
$-\delta(p)^{-}(\sigma)=-p\cdot\partial(\sigma)$ when $p\cdot\partial(\sigma)$
is negative, and $-\delta(p)^{-}(\sigma)=0$ otherwise. The second constraint
and the finiteness of the solution is satisfied by the fact that
$p(\gamma)=-1$. ∎

Lemma 4.1 tells us that a solution to LP2 yields a directed combinatorial
$\gamma$-cut. Recall, by Proposition 3.3 every $\gamma$-cut $p$ yields a
directed combinatorial $\gamma$-cut by taking the coboundary
$\delta(p)=\sum\alpha_{i}\sigma_{i}$ and considering the negative components
$\delta(p)^{-}=\\{\sigma_{i}\mid\alpha_{i}<0\\}$. By Lemma 4.1 $\delta(p)^{-}$
is a feasible solution to LP2; the cost of this solution is
$c\cdot\delta(p)^{-}$. The coefficients $\alpha_{i}$ need not always equal
one; hence in general we have $\|C\|\neq c\cdot\delta(p)^{-}$. It follows that
LP2 need not return a minimum directed combinatorial $\gamma$-cut. In Theorem
4.3 we will give conditions describing when LP2 returns a directed
combinatorial $\gamma$-cut. To conclude the section we state our main theorem
about LP2 whose proof is immediate from Lemmas 4.1 and 4.1.

######  Theorem 4.1.

Let $y=[y_{d-1},y_{d}]^{T}$ be an optimal solution to LP2. The set
$\textsf{supp}(y_{d})$ is a directed combinatorial $\gamma$-cut such that
$y_{d}=\delta(y_{d-1})^{-}$. Moreover, $y_{d}$ minimizes $c\cdot\delta(p)^{-}$
where $p$ ranges over all $\gamma$-cuts.

###  4.2 Integral solutions

In this section we provide an example of a simplicial flow network with
integral capacity constraints and fractional maximum flow. By Theorem 2.1 such
a network must contain some relative torsion. This is achieved by the
inclusion of a Möbius strip in our simplicial flow network. Our example will
be used later in Theorem 4.2 showing that computing a maximum integral flow in
a simplicial flow network is NP-hard.

Figure 1: A triangulated disk $\mathcal{D}$ (left) and Möbius strip
$\mathcal{M}$ (right). The Möbius strip has two points on its boundary
identified forming the vertex $u$. In red we have the input cycle (a figure-
eight) $\gamma$ and we set $\alpha=uwvu$. We orient the complex such that
$\partial\mathcal{M}=\gamma+2\alpha$ and $\partial\mathcal{D}=-\alpha$. The
capacity on each simplex in both the disk and Möbius strip is one.

#### Fractional maximum flow

We will now explicitly describe a simplicial flow network with integral
capacities whose maximum flow value is fractional. Let $\mathcal{M}$ be a
triangulated Möbius strip with boundary $\partial\mathcal{M}=2\alpha+\gamma$
such that two vertices in $\alpha$ have been identified making $\alpha$ a
simple cycle. This identification makes $\gamma$ a figure-eight. Now let
$\mathcal{D}$ be a triangulated disk oriented such that
$\partial\mathcal{D}=-\alpha$. See Figure 1 for an illustration. Call the
resulting complex $\mathcal{M}\mathcal{D}$. The capacity function $c$ has
$c(t)=1$ for each triangle $t\in\mathcal{M}\mathcal{D}$. Now we solve the max-
flow problem on $(\mathcal{M}\mathcal{D},c,\gamma)$. Note that for any flow
$f$ we have $f(t_{1})=f(t_{2})$ for all triangles $t_{1},t_{2}\in\mathcal{M}$;
moreover, for all $t_{1},t_{2}\in\mathcal{D}$ we also have
$f(t_{1})=f(t_{2})$. The value of any flow $f$ on
$(\mathcal{M}\mathcal{D},c,\gamma)$ is equal to its value on $\mathcal{M}$,
and in order to maintain conservation of flow we must have
$f(\mathcal{D})=2f(\mathcal{M})$. Now, the capacity constraints imply that the
maximum flow $f$ has $f(\mathcal{M})=1/2$ and $f(\mathcal{D})=1$ . We have
$\partial
f=\frac{1}{2}\partial\mathcal{M}+\partial\mathcal{D}=\frac{1}{2}\gamma+\alpha-\alpha$.
Hence, $\|f\|=1/2$.

#### Maximum integral flow

Given a simplicial flow network $(\mathcal{K},c,\gamma)$ with integral
capacities we consider the problem of finding the maximum integral flow. That
is, a $d$-chain $f\in C_{d}(\mathcal{K},\mathbb{Z})$ obeying the capacity
constraints such that $\partial f=k\gamma$ where $k\in\mathbb{Z}$ is
maximized. We show the problem is NP-hard by a reduction from graph
3-coloring. Our reduction is inspired by a MathOverflow post from Sergei
Ivanov showing that finding a subcomplex homeomorphic to the 2-sphere is NP-
hard [18]. In the appendix we adapt the proof to show that the high
dimensional generalization of computing a directed path in a graph is also NP-
hard. Given a graph $G$ we construct a 2-dimensional simplicial flow network
whose maximum flow is integral if and only if $G$ is 3-colorable.

######  Theorem 4.2.

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network where $\mathcal{K}$
is a 2-complex and $c$ is integral. Computing a maximum integral flow of
$(\mathcal{K},c,\gamma)$ is NP-hard.

###### Proof.

Let $G=(V,E)$ be a graph. We will construct a simplicial flow network
$(\mathcal{K},c,\gamma)$ such that its maximum flow is integral if and only if
$G$ is 3-colorable.

We start our construction with a punctured sphere $\mathcal{S}$ containing
$|V|+1$ boundary components called $\gamma$ and $\beta_{v}$ for each $v\in V$.
For each boundary component $\beta_{v}$ we construct three disks
$R_{v},B_{v},G_{v}$ each with boundary $-\beta_{v}$. These disks represent the
three colors in our coloring: red, blue, and green. We refer to these disks as
color disks and use $\mathcal{C}_{v}$ to denote an arbitrary color disk
associated with $v$ and use $k\in\\{r,b,g\\}$ to denote an arbitrary color. On
each color disk $\mathcal{C}_{v}$ we add a boundary component for each edge
$e=(u,v)$ incident to $v$. By $\beta_{v,e,k}$ we denote the boundary component
corresponding to the vertex $v$, edge $e$, and color $k$. For each edge
$e=(u,v)$ and each pair of boundary components $\beta_{u,e,k_{u}}$ and
$\beta_{v,e,k_{v}}$ with $k_{u}\neq k_{v}$ we construct a tube with boundary
components $-\beta_{u,e,k_{u}}$ and $-\beta_{v,e,k_{v}}$ denoted
$\mathcal{T}_{e,k_{u},k_{v}}$. When $k_{u}=k_{v}=k$ we construct a tube
$\mathcal{T}_{e,k,k}$ and puncture it with a third boundary component $\alpha$
and construct a negatively oriented real projective plane
$\mathcal{R}\mathcal{P}_{e,k}$ with boundary
$\partial\mathcal{R}\mathcal{P}_{e,k}=-2\alpha$. We call the resulting complex
$\mathcal{K}$ and assign a capacity $c(\sigma)=1$ for every triangle $\sigma$
in $\mathcal{K}$.

We will show that a maximum integral flow $f$ of $\mathcal{K}$ has $\|f\|=1$
if and only if $G$ is 3-colorable. The following four properties of a maximum
integral flow $f$ imply that $G$ is 3-colorable.

  * •

$f$ must assign exactly one unit of flow to each triangle in $\mathcal{S}$
since the value of $f$ is equal to $f(\mathcal{S})$.

  * •

For each vertex $v\in V$ exactly one color disk $\mathcal{C}_{v}$ is assigned
one unit of flow while the other two color disks associated with $v$ are
assigned zero units of flow. Otherwise, either conservation of flow is
violated or some color disk is assigned a fractional flow value.

  * •

For each edge $e=(u,v)\in E$ exactly one tube $\mathcal{T}_{e,k_{u},k_{v}}$
with $k_{u}\neq k_{v}$ must be assigned one unit of flow with all other tubes
associated with $e$ assigned zero units of flow. The tube
$\mathcal{T}_{e,k_{u},k_{v}}$ assigned one unit of flow is the tube connecting
the color disks $\mathcal{C}_{v}$ and $\mathcal{C}_{u}$ that are assigned one
unit of flow by the previous property.

  * •

$f$ assigns zero flow to every $\mathcal{T}_{e,k,k}$ and
$\mathcal{R}\mathcal{P}_{e,k}$ since otherwise the triangles in
$\mathcal{R}\mathcal{P}_{e,k}$ would need to have $1/2$ units of flow assigned
to them to maintain conservation of flow.

These four properties imply that the set of color disks
$\\{\mathcal{C}_{v}\mid f(\sigma)=1,\,\forall\sigma\in\mathcal{C}_{v}\\}$
corresponds to a 3-coloring of $G$. Conversely, given a 3-coloring of $G$ we
assign a flow value of one to each color disk corresponding to the 3-coloring.
We extend this assignment to a $\gamma$-flow of value one by assigning a flow
value of one to $\mathcal{S}$ and the tubes corresponding to the 3-coloring. ∎

###  4.3 Integral cuts

The goal of this section is to show that for simplicial complexes relative
torsion-free in dimension $d-1$ there exists optimal solutions to LP2 whose
support is a minimum combinatorial $\gamma$-cut. Note that by Theorem 2.1 a
simplicial complex that is relative torsion-free in dimension $d-1$ has a
totally unimodular $d$-dimensional boundary matrix. The total unimodularity is
key to our proof. However, we first provide an example of a complex (with
relative torsion) whose optimal solution’s support does not form a minimum
combinatorial $\gamma$-cut. Our construction is a slight modification of
$\mathcal{M}\mathcal{D}$ defined in Section 4.2.

Consider the simplicial complex constructed by taking $\mathcal{M}\mathcal{D}$
and glueing a wedge sum of two disks $\mathcal{W}$ along the figure-eight
$\gamma$. That is, $\partial\mathcal{W}=\gamma$. We give every triangle in the
resulting complex a capacity equal to one. A maximum $\gamma$-flow has value
$3/2$, so the dual program finds a $\gamma$-cut of the same value. One
potential optimal solution is a $(d-1)$-cochain whose coboundary assigns a
value of $-1/2$ to two triangles in $\mathcal{W}$ and a value of $-1/2$ to one
triangle in $\mathcal{D}$. The support of this coboundary has weight equal to
three, however a minimal combinatorial $\gamma$-cut has weight two by taking
only one triangle from $\mathcal{W}$ and one from $\mathcal{D}$. See Figure 2
for an illustration.

Figure 2: The simplicial complex $\mathcal{M}\mathcal{D}$ with a wedge sum of
two disks $\mathcal{W}$ identified to the figure-eight $\gamma$. In red we
have a 1-cochain which assigns a value of $-1/2$ to each red edge. The
coboundary of the red cochain assigns a value of $-1/2$ to one triangle in
$\mathcal{D}$ and a value of $-1/2$ to two triangles in $\mathcal{W}$. The
value of the red cochain coincides with the value of the maximum
$\gamma$-flow. However, its support is not a minimum combinatorial
$\gamma$-cut. A minimum combinatorial $\gamma$-cut picks one triangle from
$\mathcal{D}$ and one triangle from $\mathcal{W}$.

Now, we show that when $\mathcal{K}$ is relative torsion-free in dimension
$d-1$ LP2 has an optimal solution whose support is a minimum directed
combinatorial $\gamma$-cut. Specifically, we show that a solution existing on
a vertex of the polytope defined by the constraints of LP2 is a cochain
$y_{d-1}$ with negative coboundary $y_{d}$ such that
$y_{d}(\sigma)\in\\{0,1\\}$ for all $\sigma\in\mathcal{K}^{d}$ hence $\sum
y_{d}(\sigma)c(\sigma)=\|\textsf{supp}(y_{d})\|$. That is, the value of a
vertex solution to LP2 is equal to the cost of $\textsf{supp}(y_{d})$ as a
directed combinatorial $\gamma$-cut.

######  Theorem 4.3.

Let $\mathcal{K}$ be $d$-dimensional simplicial complex that is relative
torsion-free in dimension $d-1$ and $y=[y_{d-1},y_{d}]^{T}$ be an optimal
vertex solution to the dual program. The set $\textsf{supp}(y_{d})$ is a
minimum directed combinatorial $\gamma$-cut.

###### Proof.

We can write the constraint matrix of LP2 as the $2n_{d}\times(n_{d}+n_{d-1})$
block matrix

$A=\begin{bmatrix}\delta&I_{n_{d}}\\\ 0_{n_{d}}&I_{n_{d}}\end{bmatrix}.$

Since $\mathcal{K}$ is relative torsion-free in dimension $d-1$ Theorem 2.1
tells us that $\partial_{d}$ is totally unimodular; further, we have that
$\partial^{T}=\delta$ is also totally unimodular. Total unimodularity is
preserved under the operation of adding a row or column consisting of exactly
one component equal to $1$ and the remaining components equal to $0$, so $A$
is totally unimodular [26, Section 19.4]. We write LP2 as the linear system
$Ax\geq b$ where $b$ is a $n_{d}+n_{d-1}$ dimensional vector with exactly one
component equal to $1$ and the remaining components equal to $0$. Let
$y=[y_{d-1},y_{d}]^{T}$ be an optimal vertex solution to LP2. For every
$(d-1)$-simplex $\tau\in\mathcal{K}^{d-1}$ we either have $y_{d-1}(\tau)\geq
0$ or $y_{d-1}(\tau)\leq 0$. Let $I^{\prime}_{n_{d-1}}$ be the matrix whose
rows correspond to these inequalities. Note that $I^{\prime}_{n_{d-1}}$ is a
diagonal matrix with entries in $\\{-1,1\\}$. Now we consider the
$(2n_{d}+n_{d-1})\times(n_{d}+n_{d-1})$ dimensional linear system
$A^{\prime}x\geq b^{\prime}$ where

$A^{\prime}=\begin{bmatrix}\delta&I_{n_{d}}\\\ 0&I_{n_{d}}\\\
I^{\prime}_{n_{d-1}}&0\end{bmatrix}$

and $b^{\prime}$ is constructed by appending extra zeros to $b$. We construct
$y^{\prime}$ from $y$ similarly. Note that $A^{\prime}$ is totally unimodular
and $y^{\prime}$ is a vertex solution of the system. There exists a vertex $v$
of the polyhedron $P\subseteq\mathbb{R}^{n_{d}+n_{d-1}}$ corresponding to the
linear system such that $A^{\prime}y^{\prime}=v\geq b^{\prime}$ such that
$n_{d-1}+n_{d}$ constraints are linearly independent and tight. Hence, there
is an $(n_{d-1}+n_{d})\times(n_{d-1}+n_{d})$ square submatrix
$A^{\prime\prime}$ with $A^{\prime\prime}y^{\prime}=b^{\prime\prime}$ where
$b^{\prime\prime}$ is $b^{\prime}$ restricted to the tight constraints. We
will use Cramer’s rule to show that the vertex solution $y$ has components
coming from the set $\\{-1,0,1\\}$. Let
$A^{\prime\prime}_{i,b^{\prime\prime}}$ be the matrix obtained by replacing
the $i^{\text{th}}$ column of $A^{\prime\prime}$ with $b^{\prime\prime}$. By
Cramer’s rule we compute the $i^{\text{th}}$ component of $y$ as
$y_{i}=\frac{\det(A^{\prime\prime}_{i,b^{\prime\prime}})}{\det(A^{\prime\prime})}$.
Since both $A^{\prime\prime}_{i,b^{\prime\prime}}$ and $A^{\prime\prime}$ are
totally unimodular we have $v_{i}\in\\{-1,0,1\\}$. Further, we know that
$A^{\prime\prime}$ is non-singular because it corresponds to linearly
independent constraints.

By the above argument we know that an optimal solution $y$ to LP2 has all of
its components contained in the set $\\{-1,0,1\\}$. The constraint $y_{d}\geq
0$ means that for all $d$-simplices $\sigma$ we have
$y_{d}(\sigma)\in\\{0,1\\}$ and
$\sum_{\sigma\in\mathcal{K}^{d}}y_{d}(\sigma)c(\sigma)=\|\textsf{supp}(y_{d})\|$.
Hence, $\textsf{supp}(y_{d})$ is a minimum directed combinatorial
$\gamma$-cut. ∎

##  5 Embedded simplicial complexes

In this section we consider a simplicial flow network $(\mathcal{K},c,\gamma)$
where $\mathcal{K}$ is a $d$-dimensional simplicial complex with an embedding
into $\mathbb{R}^{d+1}$. Alexander duality implies that
$\mathbb{R}^{d+1}\setminus\mathcal{K}$ consists of $\beta_{d}+1$ connected
components. We call these connected components voids; exactly one void is
unbounded and we denote the voids by $V_{i}$ for $1\leq i\leq\beta_{d+1}$.
Given an embedding into $\mathbb{R}^{d+1}$, computing the voids of
$\mathcal{K}$ can be done in polynomial time [8]. Further, we assume that the
$d$-simplices are consistently oriented with respect to the voids. The
embedding guarantees that every $d$-simplex $\sigma$ appears on the boundary
of at most two voids; by our assumption if $\sigma$ appears on the boundary of
two voids then it most be oriented positively on one and negatively on the
other. We denote the boundary of the void $V_{i}$ by
$\operatorname{Bd}(V_{i})$. Every $d$-simplex contained in the support of some
$d$-cycle is on the boundaries of exactly two voids; it follows that the
boundaries of any set of $\beta_{d}$ voids is a basis of $H_{d}(\mathcal{K})$.

In order to state our theorems we need one additional assumption on
$\mathcal{K}$. We assume there exists some void $V_{i}$ containing two unit
$\gamma$-flows $\Gamma_{1},\Gamma_{2}$ whose supports partition
$\operatorname{Bd}(V_{i})$:
$\textsf{supp}(\Gamma_{1})\cap\textsf{supp}(\Gamma_{2})=\emptyset$ and
$\textsf{supp}(\Gamma_{1})\cup\textsf{supp}(\Gamma_{2})=\operatorname{Bd}(V_{i})$.
This assumption makes our problem analogous to an $st$-flow network in a
planar graph such that $s$ and $t$ appear on the same face. The existence of
two unit $\gamma$-flows partitioning the boundary is analogous to the two
disjoint $st$-paths on the boundary of the face. It will be convenient to take
the negation of $\Gamma_{1}$ and treat it as a unit $(-\gamma)$-flow;
otherwise the assumption conflicts with the assumed consistent orientation.
This is equivalent as it does not change the support of the flow, so for the
rest of the section we will take $\Gamma_{1}$ to be a unit $(-\gamma)$-flow.

From $\mathcal{K}$ we construct its directed dual graph $\mathcal{K}^{*}$ as
follows. Each void becomes a vertex of $\mathcal{K}^{*}$. Each $d$-simplex on
the boundary of two voids becomes an edge; since we assumed the $d$-simplices
are consistently oriented we direct the dual edge from the negatively oriented
void to the positively oriented void. The remaining $d$-simplices only appear
on one void and become loops in $\mathcal{K}^{*}$. For a $d$-simplex $\sigma$
on the boundary of voids $u$ and $v$ we denote its corresponding dual edge
$\sigma^{*}=(u^{*},v^{*})$ and we weight the edges by the capacity function:
$c^{*}(\sigma^{*})=c(\sigma)$. Let $v_{i}^{*}$ be the vertex dual to the void
whose boundary is partitioned by $\textsf{supp}(\Gamma_{1})$ and
$\textsf{supp}(\Gamma_{2})$. We split $v_{i}^{*}$ into two new vertices
denoted $s^{*}$ and $t^{*}$. The edges incident to $v_{i}^{*}$ whose dual
$d$-simplices were contained in $\textsf{supp}(\Gamma_{1})$ become incident to
$s^{*}$, and the edges whose dual $d$-simplices were contained in
$\textsf{supp}(\Gamma_{2})$ become incident to $t^{*}$. We add the directed
edge $(t^{*},s^{*})$ and set its capacity to infinity;
$c^{*}((t^{*},s^{*}))=\infty$. Returning to the analogy of a planar graph with
$s$ and $t$ on the same face, splitting $v_{i}^{*}$ is analogous to adding an
additional edge from $t$ to $s$ which splits their common face into two.
However, for our purposes we are only concerned with the algebraic properties
of the construction and do not actually need to modify the simplicial complex.

We need to update the chain complex associated with $\mathcal{K}$ to account
for the voids and the splitting of $v_{i}^{*}$. We add an additional basis
element $\Sigma$ to $C_{d}(\mathcal{K})$ such that $\partial\Sigma=\gamma$ and
give it infinite capacity; $c(\Sigma)=\infty$. In our construction $\Sigma$ is
dual to the edge $(t^{*},s^{*})$. In our planar graph analogy $\Sigma$ plays
the role of an edge from $t$ to $s$ drawn entirely in the outer face; to make
this precise we will need to add an additional chain group
$C_{d+1}(\mathcal{K})$. We add each void $V_{j}$ with $j\neq i$ as a basis
element of $C_{d+1}(\mathcal{K})$ and define the boundary operator as
$\partial_{d+1}V_{j}=\sum_{\sigma\in\text{Bd}(v)}(-1)^{k_{\sigma}}\sigma$
where $k_{\sigma}=0$ if $\sigma$ is oriented positively on $V_{j}$ and
$k_{\sigma}=1$ if $\sigma$ is oriented negatively on $V_{j}$. Next we add
additional basis elements $S$ and $T$ whose boundaries are defined by
$\partial_{d+1}S=\Gamma_{1}+\Sigma$ and $\partial_{d+1}T=\Gamma_{2}-\Sigma$.
The inclusion of $C_{d+1}(\mathcal{K})$ results in a valid chain complex since
by definition the image of $\partial_{d+1}$ under each basis element is a
$d$-cycle. Moreover, in the new complex we have $H_{d}(\mathcal{K})\cong 0$
since the boundaries of the voids generate $H_{d}(\mathcal{K})$.

Given our new chain complex we can extend the dual graph $\mathcal{K}^{*}$ to
a dual complex; this construction is reminiscent of the dual of a polyhedron.
We define the dual complex by the isomorphism of chain groups
$C_{k}(\mathcal{K}^{*})\cong C_{d-k+1}(\mathcal{K})$. The dual boundary
operator $\partial^{*}_{k}\colon C_{k}(\mathcal{K}^{*})\rightarrow
C_{k-1}(\mathcal{K}^{*})$ is the coboundary operator $\delta_{d-k+2}$, and the
dual coboundary operator $\delta^{*}_{k}\colon
C_{k-1}(\mathcal{K}^{*})\rightarrow C_{k}(\mathcal{K}^{*})$ is the boundary
operator $\partial_{d-k+2}$. The primal boundary operator commutes with the
dual coboundary operator, and the primal coboundary operator commutes with the
dual boundary operator. We summarize the duality in the following diagram.

${C_{d+1}(\mathcal{K})}$${C_{d}(\mathcal{K})}$${\dots}$${C_{0}(\mathcal{K})}$${C_{0}(\mathcal{K}^{*})}$${C_{1}(\mathcal{K}^{*})}$${\dots}$${C_{d+1}(\mathcal{K}^{*})}$$\scriptstyle{\cong}$$\scriptstyle{\partial_{d+1}}$$\scriptstyle{\cong}$$\scriptstyle{\partial_{d}}$$\scriptstyle{\delta_{d+1}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{\delta_{d}}$$\scriptstyle{\delta_{1}}$$\scriptstyle{\cong}$$\scriptstyle{\delta^{*}_{1}}$$\scriptstyle{\partial^{*}_{1}}$$\scriptstyle{\delta^{*}_{2}}$$\scriptstyle{\partial^{*}_{2}}$$\scriptstyle{\delta^{*}_{d+1}}$$\scriptstyle{\partial_{d+1}^{*}}$

We now have enough structure to state our duality theorems. In Section 5.1 we
show that computing a max-flow for $(\mathcal{K},c,\gamma)$ is equivalent to
computing a shortest path from $s^{*}$ to $t^{*}$ in $\mathcal{K}^{*}$. In
Section 5.2 we show that computing a minimum cost $\gamma$-cut $p$ is
equivalent to computing a minimum cost unit $s^{*}t^{*}$-flow in
$\mathcal{K}^{*}$.

###  5.1 Max-flow / shortest path duality

We compute a shortest path from $s^{*}$ to $t^{*}$ in $\mathcal{K}^{*}$ using
a well-known shortest paths linear program. Details on the linear program can
be found in [11].

maximize $\displaystyle\quad\textsf{dist}(t^{*})$ (LP3) subject to
$\displaystyle\quad\textsf{dist}(s^{*})=0$
$\displaystyle\quad\textsf{dist}(v^{*})-\textsf{dist}(u^{*})\leq
c^{*}((u^{*},v^{*}))$ $\displaystyle\forall\,(u^{*},v^{*})\in E$

The solution to LP3 is a function $\textsf{dist}\colon
V(\mathcal{K}^{*})\rightarrow\mathbb{R}$ which maps a vertex to its distance
from $s^{*}$ under the weight function $c$. By duality, dist is a
$(d+1)$-cochain mapping the voids to $\mathbb{R}$. In the following theorem we
will show that dist is equivalent to a $\gamma$-flow with value equal to
$\textsf{dist}(t^{*})$.

######  Theorem 5.1.

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network where $\mathcal{K}$
is a $d$-dimensional simplicial complex embedded into $\mathbb{R}^{d+1}$ with
two unit $\gamma$-flows whose supports partition the boundary of some void
$\operatorname{Bd}(V_{i})$. There is a bijection between $\gamma$-flows of
$(\mathcal{K},c,\gamma)$ and $s^{*}t^{*}$-paths in $\mathcal{K}^{*}$ such that
the value of a $\gamma$-flow equals the length of its corresponding
$s^{*}t^{*}$-path.

###### Proof.

Recall, by our discussion in Section 3 there is a value-preserving bijection
between $\gamma$-flows and $\gamma$-circulations in $\mathcal{K}$ and the
value of a $\gamma$-circulation $f$ is given by $f(\Sigma)$. We can write $f$
as a linear combination of $d$-cycles and by our construction there is a basis
for the $d$-cycle space given by $\beta_{d}$ elements of
$\operatorname{im}\partial_{d+1}$. To form our basis we pick every element of
$\operatorname{im}\partial_{d+1}$ except $\partial_{d+1}S$. Hence, $f$ can be
written as a linear combination
$f=\sum_{i=0}^{\beta_{d}-1}\alpha_{i}B_{i}+\alpha_{T}B_{T}$ where
$\partial_{d+1}V_{i}=B_{i}$ and $\partial_{d+1}B_{T}=T$. We construct a
$(d+1)$-cochain $P$ by the mapping $P(V_{i})=\alpha_{i}$, $P(S)=0$,
$P(T)=\alpha_{T}$. Dual to $P$ is a $0$-cochain on the vertices of
$\mathcal{K}^{*}$ which we call dist. By construction we have
$\textsf{dist}(s^{*})=0$. Since $\mathcal{K}$ is consistently oriented on the
voids and $f$ obeys the capacity constraints we have
$\textsf{dist}(v^{*})-\textsf{dist}(u^{*})\leq c^{*}((u^{*},v^{*}))$ for every
edge $(u^{*},v^{*})$. Finally, we have $\textsf{dist}(t^{*})=f(\Sigma)$ since
$f(\Sigma)=P(T)-P(S)=\alpha_{T}$.

Conversely, let dist be some vector satisfying the constraints of LP3. As dist
is a cochain on the vertices of $\mathcal{K}^{*}$ by duality we may view dist
as an element of $C_{d+1}(\mathcal{K})$ hence $\partial(\textsf{dist})$ is a
circulation in $\mathcal{K}$ obeying the capacity constraints. Further, we
have that the component of $\partial(\textsf{dist})$ indexed by $\Sigma$ is
equal to $\textsf{dist}(t^{*})-\textsf{dist}(s^{*})=\textsf{dist}(t^{*})$.
Hence, $\|\partial(\textsf{dist})\|=\textsf{dist}(t^{*})$ which completes the
proof. ∎

###  5.2 Min-cut / min cost flow duality

We begin this section by stating the minimum cost flow problem in graphs. The
minimum cost flow problem asks to find the cheapest way to send $k$ units of
flow from $s$ to $t$. An instance of the minimum cost flow problem is a tuple
$(G,w,c,k)$ where $G=(V,E)$ is a directed graph, $w,c\in C_{1}(G)$, and
$k\in\mathbb{R}$. The 1-chains represent the weight and capacity of each edge,
and $k$ is the demand of the network. The goal of the minimum cost flow
problem is to find an $st$-flow obeying the following constraints.

minimize $\displaystyle\quad\sum_{e\in E}w(e)f(e)$ subject to
$\displaystyle\quad\delta(v)\cdot f=0$ $\displaystyle\forall v\in
V\setminus\\{s,t\\}$ $\displaystyle\quad 0\leq f(e)\leq c(e)$
$\displaystyle\quad\delta(s)\cdot f=-k$ $\displaystyle\quad\delta(t)\cdot f=k$

The first two constraints are conservation of flow and capacity constraints.
The third and fourth are the demand constraints which say $f$ must send
exactly $k$ units of flow from $s$ to $t$; note that only one of these
constraints is necessary. We will compute a minimum directed $\gamma$-cut in
$\mathcal{K}$ by solving the minimum cost flow problem with $k=1$ in
$\mathcal{K}^{*}$. We assume there is a weight function
$w\colon\mathcal{K}^{d}\rightarrow\mathbb{R}^{+}$ on the $d$-skeleton of
$\mathcal{K}$, which after dualizing becomes a weight function $w^{*}$ on the
edges of $\mathcal{K}^{*}$. In the following theorem the capacity function is
not needed, so we will assume each edge in $\mathcal{K}^{*}$ has infinite
capacity.

######  Theorem 5.2.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex embedded into
$\mathbb{R}^{d+1}$ with two unit $\gamma$-flows whose supports partitions the
boundary of some void $\operatorname{Bd}(V_{i})$. There is a bijection between
$\gamma$-cuts $p$ in $\mathcal{K}$ and unit $s^{*}t^{*}$-flows $f$ in
$\mathcal{K}^{*}$ such that $\|p\|=\sum w^{*}(e)f(e)$.

###### Proof.

Let $p$ be a $\gamma$-cut in $\mathcal{K}$ and let $\bar{p}$ be its negation;
that is, $\bar{p}$ is a $(d-1)$-cochain with $\bar{p}(\gamma)=1$. By
construction we have $\delta(\bar{p})(\Sigma)=\bar{p}((\partial\Sigma)=1$. We
define $f$ to be the image of $\delta(\bar{p})$ under the duality isomorphism.
Since $\bar{p}^{*}$ is a 2-chain in $\mathcal{K}^{*}$ and
$f=\partial^{*}(\bar{p}^{*})$ we see that $f$ is a 1-circulation in
$\mathcal{K}^{*}$. By removing the edge $\Sigma^{*}=(t^{*},s^{*})$ from $f$ we
see that $f$ is an $s^{*}t^{*}$-flow with $\|f\|=1$ since
$f(\Sigma^{*})=\delta(\bar{p})(\Sigma)=1$. Finally, we have
$\|p\|=\|p^{\prime}\|=\sum w(\sigma)\delta(p)(\sigma)=\sum
w(\sigma^{*})f(\sigma^{*})$.

Conversely, let $f^{*}$ be a 1-circulation in $\mathcal{K}^{*}$ with
$f(\Sigma^{*})=1$. By assumption we have $H_{d}(\mathcal{K})\cong 0$ and by
duality $H_{1}(\mathcal{K}^{*})\cong 0$. It follows that $f^{*}$ can be
written as a linear combination of boundaries $f^{*}=\sum\alpha_{i}B^{*}_{i}$
where $B_{i}^{*}\in\operatorname{im}\partial^{*}_{2}$. Let $p^{*}$ be a
2-chain with $\partial_{2}^{*}p^{*}=f^{*}$. Dual to $f^{*}$ is a
$d$-coboundary $f=\sum\alpha_{i}B_{i}$ where
$B_{i}\in\operatorname{im}(\delta_{d})$ and dual to $p^{*}$ is a
$(d-1)$-cochain $p$ with $\delta(p)=f$. We have that $\bar{p}$ is a
$\gamma$-cut since
$\bar{p}(\gamma)=\bar{p}(\partial\Sigma)=\delta(\bar{p})(\Sigma)=-f(\Sigma)=-f^{*}(\Sigma^{*})=-1$.
Finally, we have $\sum
w^{*}(e)f^{*}(e)=\sum|w(\sigma)\delta(p)(\sigma)|=\|p\|=\|\bar{p}\|$. ∎

######  Corollary .

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex embedded in
$\mathbb{R}^{d+1}$ with two unit $\gamma$-flows partitioning some
$\operatorname{Bd}(V_{i})$. There is a polynomial time algorithm computing a
minimum directed combinatorial $\gamma$-cut.

###### Proof.

We solve the minimum cost circulation problem in $\mathcal{K}^{*}$ setting the
demand and every capacity constraint equal to one. The resulting flow is dual
to a $\gamma$-cut $p$ in $\mathcal{K}$. Since the minimum cost circulation is
integral we have $\|\textsf{supp}(\delta(p))\|=\|p\|$. That is, the cost of
$p$ as a $\gamma$-cut equals the cost of $\textsf{supp}(\delta(p))$ as a
combinatorial $\gamma$-cut. ∎

##  6 Ford-Fulkerson algorithm

In this section we show how the Ford-Fulkerson algorithm can be used to
compute a maximum flow of simplicial flow network $(\mathcal{K},c,\gamma)$. In
a simplicial flow network the Ford-Fulkerson algorithm picks out a augmenting
chain at every iteration which is a high dimensional generalization of an
augmenting path. As shown in Section 4.2 a maximum flow of a simplicial flow
network with integral capacities may not be integral, so it is not immediate
that Ford-Fulkerson is guaranteed to halt. To remedy this, our implementation
of Ford-Fulkerson contains a heuristic reminiscent of the network simplex
algorithm. Our heuristic guarantees that at every iteration of Ford-Fulkerson
the flow is a solution on a vertex of the polytope defined by the linear
program. Hence, our heuristic makes our implementation of Ford-Fulkerson into
a special case of the simplex algorithm. It follows that Ford-Fulkerson does
halt on a simplicial flow network, but the running time may be exponential.
Our heuristic for picking augmenting chains takes $O(n^{\omega+1})$ time since
it requires solving $O(n)$ linear systems, each taking $O(n^{\omega})$ time
using standard methods [19]. In Section 6.3 we show that solving a particular
type of linear system reduces to finding an augmenting chain, giving us an
imprecise lower bound on the complexity of our heuristic.

We begin this section by defining the concepts of the residual complex and of
augmenting chains which serve as high dimensional generalizations of the
residual graph and augmenting paths used in the Ford-Fulkerson algorithm for
graphs. We show that a flow is maximum if and only if its residual complex
contains no augmenting chains, generalizing the well-known graph theoretic
result. This work is an extension of previous work done by Latorre who showed
one direction of the theorem and leaving the other open [22].

###  6.1 The residual complex

We now present our definitions of the residual complex and an augmenting
chain.

######  Definition 5 (Residual complex).

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network and $f$ be a
feasible flow on the network. We define a new simplicial flow network called
the residual complex to be the tuple $(\mathcal{K}_{f},c_{f},\gamma)$
constructed in the following way. The $d$-skeleton of $\mathcal{K}_{f}$ is the
union $\mathcal{K}^{d}\cup-\mathcal{K}^{d}$, that is, for each $d$-simplex
$\sigma$ in $\mathcal{K}$ we add an additional $d$-simplex $-\sigma$ whose
orientation is opposite of $\sigma$.
$\mathcal{K}_{f}^{d^{\prime}}=\mathcal{K}^{d^{\prime}}$ for dimensions
$d^{\prime}<d$. The residual capacity function
$c_{f}\colon\mathcal{K}^{d}_{f}\rightarrow\mathbb{R}$ is given by

$c_{f}(\sigma)=\begin{cases}c(\sigma)-f(\sigma)&\sigma\in\mathcal{K}^{d},\\\
f(\sigma)&-\sigma\in\mathcal{K}^{d}.\end{cases}$

######  Definition 6 (Augmenting chain).

Let $\mathcal{K}_{f}$ be a residual complex for the simplicial flow network
$(\mathcal{K},c,\gamma)$. An augmenting chain is a $d$-chain $\Gamma\in
C_{d}(\mathcal{K}_{f})$ such that $\Gamma=\sum\alpha_{i}\sigma_{i}$ and
$\partial\Gamma=\gamma$ with $\alpha_{i}\geq 0$.

Note that an augmenting chain need not obey the residual capacity constraint
$c_{f}$. This is because after finding an augmenting chain the amount of flow
sent through the chain will be normalized by the coefficients $\alpha_{i}$
producing a new chain respecting the capacity constraints. The following two
lemmas prove the main result of the section. The first of which was observed
by Latorre [22].

######  Lemma  (Latorre [22]).

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network. If $f$ is a maximum
flow then $\mathcal{K}_{f}$ contains no augmenting chains.

###### Proof.

Let $\Gamma=\sum\alpha_{i}\sigma_{i}$ be an augmenting chain in
$\mathcal{K}_{f}$ and let
$\alpha=\min\\{\frac{1}{\alpha_{i}}c_{f}(\sigma_{i})\\}$. Define the new flow
as follows

$f^{\prime}(\sigma)=\begin{cases}f(\sigma)+\alpha\cdot\alpha_{i}&\sigma=\sigma_{i},\\\
f(\sigma)-\alpha\cdot\alpha_{i}&-\sigma=\sigma_{i}.\end{cases}$

We have $f(\sigma_{i})+\alpha\cdot\alpha_{i}\leq
f(\sigma_{i})+c_{f}(\sigma_{i})=c(\sigma_{i})$ and
$f(\sigma_{i})-\alpha\cdot\alpha_{i}\geq f(\sigma_{i})-c_{f}(\sigma_{i})=0$ so
$f^{\prime}$ obeys the capacity constraints. To show that $f^{\prime}$ obeys
conservation of flow we compute the following equality

$\sum_{\sigma\in\mathcal{K}^{d}}f^{\prime}(\sigma)\partial(\sigma)=\sum_{\sigma\in\mathcal{K}^{d}\setminus\textsf{supp}(\Gamma)}f(\sigma)\partial(\sigma)+\sum_{\sigma_{i}\in\textsf{supp}(\Gamma)}(f(\sigma_{i})\pm\alpha\cdot\alpha_{i})\partial(\sigma_{i})=\alpha\cdot\partial\left(\sum_{\sigma_{i}\in\textsf{supp}(\Gamma)}\alpha_{i}\sigma_{i}\right)=0.$

∎

######  Lemma .

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network. If $f$ is a flow
such that $\mathcal{K}_{f}$ contains no augmenting chains then $f$ is a
maximum flow.

###### Proof.

By way of contradiction assume that $f$ is not a maximum flow and $g$ is some
other flow with higher value than $f$. We show that the $d$-chain $g-f$ is an
augmenting chain in $\mathcal{K}_{f}$. First, we note that the boundary of
$g-f$ is equal to $(\|g\|-\|f\|)\gamma$ implying $g-f$ obeys conservation of
flow, so all that remains is to check that $g-f$ obeys the capacity
constraints in $\mathcal{K}_{f}$. Let $\sigma$ be a $d$-simplex in
$\mathcal{K}$, there are two cases to consider. First, if $f(\sigma)\leq
g(\sigma)$ we have $g(\sigma)-f(\sigma)\leq c(\sigma)-f(\sigma)=c_{f}(\sigma)$
and the capacity constraint is obeyed. Second, if $g(\sigma)<f(\sigma)$ we
interpret this as applying $|g(\sigma)-f(\sigma)|$ flow to $-\sigma$. Hence,
$|g(\sigma)-f(\sigma)|=f(\sigma)-g(\sigma)<f(\sigma)=c_{f}(\sigma)$ which
concludes the proof. ∎

Lemmas 6.1 and 6.1 give us the main theorem of the section.

######  Theorem 6.1.

Let $(\mathcal{K},c,\gamma)$ be a simplicial flow network. A flow $f$ is a
maximum flow if and only if $\mathcal{K}_{f}$ contains no augmenting chains.

###  6.2 Augmenting chain heuristic

In this section we provide a heuristic for the Ford-Fulkerson algorithm that
is guaranteed to halt on a simplicial flow network. Our example in Section 4.2
shows that a maximum flow may have fractional value, so it’s not immediately
clear that Ford-Fulkerson halts on all simplicial flow networks. To remedy
this our heuristic ensures that at each step the flow corresponds to a vertex
of the flow polytope (defined in the next paragraph). As there are a finite
number of vertices, and the value of the flow increases at every step, it
follows that under this heuristic Ford-Fulkerson must halt. Under our
heuristic Ford-Fulkerson becomes a special case of the simplex algorithm. Our
heuristic is reminiscent of the network simplex algorithm which maintains a
tree at every iteration. See the book by Ahuja, Magnanti, and Orlin for an
overview of the network simplex algorithm [1].

We define the flow polytope of $(\mathcal{K},c,\gamma)$ to be the polytope
$P\subset\mathbb{R}^{n_{d}}$ defined by the constraints of the maximum flow
linear program LP1. A vertex of the polytope $P$ is any feasible solution to
LP1 with at least $n_{d}$ tight linearly independent constraints. We will
ensure that at every step of Ford-Fulkerson our flow $f$ is a vertex of $P$.
To do this we will make sure that the $d$-simplices corresponding to non-tight
constraints of LP1 form an acyclic complex. Some straightforward algebra
implies that this condition is enough to make at least $n_{d}$ constraints
tight. Let $\mathcal{H}_{f}$ be the subcomplex of $d$-simplices half-saturated
by $f$; that is, $\sigma\in\mathcal{H}_{f}$ if and only if its capacity
constraint is a strict inequality: $0<f(\sigma)<c(\sigma)$. The half-saturated
simplices do not make either of their two corresponding constraints tight,
while $d$-simplices not in $\mathcal{H}_{f}$ make exactly one of their
corresponding constraints tight. We require that $\mathcal{H}_{f}$ be an
acyclic complex at each step of Ford-Fulkerson. In the case of graphs, this
just means that $\mathcal{H}_{f}$ is a forest. For a $d$-dimensional complex
it means that $H_{d}(\mathcal{H}_{f})=0$. Acyclic complexes have been studied
by Duval, Klivans, and Martin who show that they share many properties with
forests and trees in graphs [10]. The following lemma shows that if
$\mathcal{H}_{f}$ is acyclic then $f$ is a vertex of the flow polytope.

######  Lemma .

Let $f$ be a feasible flow for the $d$-dimensional simplicial flow network
$(\mathcal{K},c,\gamma)$. If the subcomplex of half-saturated $d$-simplices
$\mathcal{H}_{f}$ is acyclic then $f$ is a vertex of the flow polytope $P$.

###### Proof.

In order for $f$ to be a vertex of $P$ we need to show that at least $n_{d}$
of the constraints of LP1 are tight, and that these $n_{d}$ tight constraints
are linearly independent. As $f$ is a flow the $2n_{d-1}$ constraints ensuring
conservation of flow are always tight. It follows that we have
$n_{d}-\beta_{d}$ tight linearly independent constraints corresponding to a
basis for $\operatorname{im}\delta_{d}$. As $\mathcal{H}_{f}$ is acyclic we
have that $|\textsf{supp}(\mathcal{H}_{f})|\leq n_{d}-\beta_{d}$ since at
least one $d$-simplex from each basis element of $H_{d}(\mathcal{K})$ must be
missing from $\mathcal{H}_{f}$. This implies that at most $2(n_{d}-\beta_{d})$
of the $2n_{d}$ capacity constraints are not tight; equivalently, at least
$2n_{d}-2(n_{d}-\beta_{d})=2\beta_{d}$ of the capacity constraints are tight.
Since $\mathcal{H}_{f}$ is acyclic we can pick a set of $\beta_{d}$
$d$-simplices $\Sigma$ such that $\dim H_{d}(\mathcal{K}\setminus\Sigma)=0$
and $\dim H_{d-1}(\mathcal{K}\setminus\Sigma)=\dim H_{d-1}(\mathcal{K})$. Each
$d$-simplex $\sigma\in\Sigma$ corresponds to some tight capacity constraint,
and since removing $\sigma$ does not change the dimension of $H_{d-1}$ it is
not contained in $\operatorname{im}\delta_{d}$. It follows that the tight
capacity constraint corresponding to $\sigma$ is linearly independent from the
$n_{d}-\beta_{d}$ conservation of flow constraints. Finally, since each tight
capacity constraint corresponds to a unique $\sigma$ they are all linearly
independent from each other. ∎

At each iteration of Ford-Fulkerson we want to pick an augmenting chain such
that the resulting flow leaves $\mathcal{H}_{f}$ acyclic. It’s not clear how
to pick such an augmenting chain. However, no matter what augmenting chain we
pick we can always repair the flow in a way that the resulting flow leaves
$\mathcal{H}_{f}$ acyclic. We describe our method for repairing the flow in
the following lemma.

######  Lemma .

Let $f$ be a feasible flow for the $d$-dimensional simplicial flow network
$(\mathcal{K},c,\gamma)$. If the subcomplex of half-saturated $d$-simplices
$\mathcal{H}_{f}$ is not acyclic then in $O(n^{\omega+1})$ time we can
construct a new flow $f^{\prime}$ such that $\mathcal{H}_{f^{\prime}}$ is
acyclic and $\|f\|=\|f^{\prime}\|$.

###### Proof.

Let $f$ be a feasible flow such that $\mathcal{H}_{f}$ is not acyclic. In
polynomial time we compute a basis for $H_{d}(\mathcal{H}_{f})$. Let
$\Sigma=\sum\alpha_{i}\sigma_{i}$ be a basis element of
$H_{d}(\mathcal{H}_{f})$ and let
$\alpha=\min\\{\frac{1}{\alpha_{i}}c_{f}(\sigma_{i})\\}$. As in Lemma 6.1 we
construct the new flow $f^{\prime}$ by

$f^{\prime}=\begin{cases}f(\sigma)+\alpha\cdot\alpha_{i}&\sigma=\sigma_{i}\\\
f(\sigma)-\alpha\cdot\alpha_{i}&-\sigma=\sigma_{i}\end{cases}.$

The new flow $f^{\prime}$ saturates some $d$-simplex in $\Sigma$ and does not
introduce any new $d$-cycles to $\mathcal{H}_{f}$ as it only affects the half-
saturated edges. We call the new subcomplex of half-saturated simplices
$\mathcal{H}_{f^{\prime}}$ and observe that $\dim
H_{d}(\mathcal{H}_{f^{\prime}})<\dim H_{d}(\mathcal{H}_{f})$. Since
$f^{\prime}$ is constructed by adding a $d$-cycle to $f$ we have that
$\|f\|=\|f^{\prime}\|$. We repeat the process of computing a homology basis
for $\mathcal{H}_{f^{\prime}}$ and saturating some basis element until
$\mathcal{H}_{f^{\prime}}$ is acyclic.

It remains to compute the running time of the above procedure. Computing a
homology basis takes $O(n^{\omega})$ time . To repair the flow we need to make
at most $O(n)$ homology basis computations, hence the total running time is
$O(n^{\omega+1})$. ∎

To wrap up the section, we state our main theorem whose proof is immediate
from Lemmas 6.2 and 6.2.

######  Theorem 6.2.

Given a simplicial flow network $(\mathcal{K},c,\gamma)$ we can compute a
maximum flow $f$ by using the Ford-Fulkerson algorithm with the following
heuristic: at every iteration pick an augmenting chain such that the
subcomplex of half-saturated $d$-simplices $\mathcal{H}_{f}$ is acyclic.

###  6.3 Lower bounds

We have shown a heuristic for which given a simplicial flow network
$(\mathcal{K},c,\gamma)$ Ford-Fulkerson is guaranteed to halt with a maximum
flow. In the worst case our algorithm runs in exponential time. In this
section we focus our attention on the time required to find an augmenting
chain. The running time of our heuristic is determined by the time it takes to
compute the augmenting chain and repair the flow at each iteration of the
algorithm. Computing the augmenting chain takes $O(n^{\omega})$ time by
solving the linear system. Repairing the flow takes $O(n^{\omega+1})$ time
since it requires $O(n)$ homology basis computations which each take time
$O(n^{\omega})$. We show that it is unlikely that this running time can be
substantially improved. More specifically, we show that finding a non-negative
solution to a linear system $Ax=b$ when $A$ has entries in $\\{-1,0,1\\}$
reduces to computing an augmenting chain for $(\mathcal{K},c,\gamma)$, hence
the complexity of solving a linear system in this form serves as a lower bound
on computing an augmenting chain. Given a linear system we construct a
2-complex with a 1-cycle $\gamma$ such that finding a 2-chain $\Gamma$ with
non-negative coefficients and $\partial\Gamma=\gamma$ is equivalent to finding
a non-negative feasible solution to the linear system. Further, the complex
$\mathcal{K}$ used in the reduction is relatively torsion-free, so the total
unimodularity of its boundary matrix cannot be used to speed up the
computation. Our reduction is essentially the same as one used by Chen and
Freedman to show homology localization over $\mathbb{Z}_{2}$ is NP-hard [6].
However, we modify it slightly since we consider coefficients over
$\mathbb{R}$. We only give a proof sketch as our reduction is almost identical
to that of Chen and Freedman’s.

######  Theorem 6.3.

Let $Ax=b$ be a linear system where $A$ has entries in $\\{-1,0,1\\}$. In
polynomial time we can construct a 2-dimensional, relatively torsion-free,
simplicial complex $\mathcal{K}$ and a 1-cycle $\gamma$ such that if a 2-chain
$\Gamma$ is an augmenting chain for $\gamma$ then it is a non-negative
solution to $Ax=b$.

###### Proof.

We construct a cell complex $\mathcal{K}$ from $A$ as follows. For each of the
$m$ rows we construct a 1-cycle $C_{i}$. For each column vector $v_{j}$ we
construct a punctured sphere $T_{j}$ with boundary components $C_{i,j},$ for
each $v_{i,j}=1$ and $-C_{i,j}$ for each $v_{i,j}=-1$. Define the 1-cycle
$\gamma$ to be $b$ with respect to the basis given by the boundary components
of $\mathcal{K}$. By our construction a vector $x=(x_{1},\dots,x_{n})$ is a
feasible solution to $Ax=b$ if and only if the 2-chain $\sum x_{i}T_{i}$ has
boundary $\gamma$. Hence, computing an augmenting chain for $\gamma$ is
equivalent to computing a non-negative solution to the linear system. It
remains to show that $\mathcal{K}$ can be triangulated into a simplicial
complex. We refer the reader to [6] for a triangulation. To see that
$\mathcal{K}$ is relatively torsion-free we refer to reader to [7] which
characterizes relative torsion in 2-complexes by forbidding certain Möbius
subcomplexes. ∎

## References

  * [1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.  Network Flows: Theory, Algorithms, and Applications.  Prentice-Hall, Inc., USA, 1993.
  * [2] J. W. Alexander.  A proof and extension of the Jordan-Brouwer separation theorem.  Transactions of the American Mathematical Society, 23(4):333–349, 1922.
  * [3] Glencora Borradaile and Philip Klein.  An $O(n\log n)$ algorithm for maximum $st$-flow in a directed planar graph.  J. ACM, 56(2), April 2009.
  * [4] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri.  Minimum cuts and shortest homologous cycles.  In Proc. 25th Ann. Symp. Comput. Geom., pages 377–385, 2009.
  * [5] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri.  Homology flows, cohomology cuts.  SIAM Journal on Computing, 41(6):1605–1634, 2012.
  * [6] Chao Chen and Daniel Freedman.  Hardness results for homology localization.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10, page 1594–1604, USA, 2010. Society for Industrial and Applied Mathematics.
  * [7] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy.  Optimal homologous cycles, total unimodularity, and linear programming.  SIAM J. Comput., 40(4):1026–1044, July 2011.
  * [8] Tamal K. Dey, Tao Hou, and Sayan Mandal.  Computing minimal persistent cycles: Polynomial and hard cases.  In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 2587–2606, USA, 2020. Society for Industrial and Applied Mathematics.
  * [9] Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin.  Cuts and flows of cell complexes.  Journal of Algebraic Combinatorics, 41:969–999.
  * [10] Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin.  Simplicial and cellular trees, pages 713–752.  Springer International Publishing, Cham, 2016.
  * [11] Jeff Erickson.  Algorithms.  http://algorithms.wtf, 2019.
  * [12] Jeff Erickson and Amir Nayyeri.  Minimum cuts and shortest non-separating cycles via homology covers.  In Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1166–1176, 2011.
  * [13] Arthur F. Veinott, Jr. and George B. Dantzig.  Integral extreme points.  SIAM Review, 10(3):371–372, July 1968.
  * [14] Greg N. Frederickson.  Fast algorithms for shortest paths in planar graphs with applications.  SIAM J. Comput., 16(6):1004–1004, 1987.
  * [15] Refael Hassin.  Maximum flow in $(s,t)$ planar networks.  Inf. Process. Lett., 13:107, 1981.
  * [16] Refael Hassin and Donald B. Johnson.  An $O(n\log^{2}n)$ algorithm for maximum flow in undirected planar networks.  SIAM J. Comput., 14(3):612–624, 1985.
  * [17] Allen Hatcher.  Algebraic topology.  Cambridge Univ. Press, Cambridge, 2000.
  * [18] Sergei Ivanov (https://mathoverflow.net/users/4354/sergei ivanov).  computational complexity.  MathOverflow.  URL:https://mathoverflow.net/q/118428 (version: 2013-01-09).
  * [19] Oscar H Ibarra, Shlomo Moran, and Roger Hui.  A generalization of the fast LUP matrix decomposition algorithm and applications.  Journal of Algorithms, 3(1):45–56, 1982.
  * [20] Alon Itai and Yossi Shiloach.  Maximum flow in planar networks.  SIAM J. Comput., 8:135–150, 1979.
  * [21] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In Proc. 43rd Ann. ACM Symp. Theory Comput., pages 313–322, 2011\.
  * [22] Fabian Latorre.  The maxflow problem and a generalization to simplicial complexes, 2012\.
  * [23] Lek-Heng Lim.  Hodge Laplacians on graphs.  SIAM Review, 63(3):685–715, 2020.
  * [24] Sarah Morell, Ina Seidel, and Stefan Weltge.  Minimum-cost integer circulations in given homology classes, 2020.
  * [25] John Reif.  Minimum $s$-$t$ cut of a planar undirected network in $O(n\log^{2}n)$ time.  SIAM J. Comput., 12:71–81, 1983.
  * [26] Alexander Schrijver.  Theory of Linear and Integer Programming.  John Wiley & Sons, Inc., USA, 1986.

##  Appendix A Directed paths in simplicial complexes

In a directed graph an $st$-path is equivalent to an 1-chain
$P=\sum\alpha_{i}e_{i}$ with $\partial P=t-s$ such that
$\alpha_{i}\in\\{0,1\\}$. The generalization to simplicial complexes is
straightforward: we define a $d$-dimensional directed $\gamma$-path in a
$d$-complex $\mathcal{K}$ to be a $d$-chain $P=\sum\alpha_{i}\sigma_{i}$ such
that $\partial P=\gamma$ and $\alpha_{i}\in\\{0,1\\}$ for all $i$. We will now
show that computing a directed $\gamma$-path is NP-complete for $d\geq 2$. The
reduction from graph 3-coloring is a slight adaptation of the proof of Theorem
4.2.

######  Theorem A.1.

Computing a directed $\gamma$-path in a $d$-dimensional simplicial complex is
NP-complete for $d\geq 2$.

###### Proof.

First, to show that computing a directed $\gamma$-path is in NP we note that
we can check the coefficients and the boundary of a 2-chain in polynomial
time. To prove NP-hardness we give a reduction from graph 3-coloring.

Given a graph $G=(V,E)$ we construct a 2-complex $\mathcal{K}$ with a boundary
component $\gamma$ such that there exists a directed $\gamma$-path if and only
if $G$ is 3-colorable. First, construct a punctured sphere with $|V|+1$
boundary components. One of these boundary components is $\gamma$, the
remaining $|V|$ are in bijection with the vertices of $G$ and we will denote
the component corresponding to the vertex $v$ as $\gamma_{v}$. For each vertex
$v$ we construct three additional punctured spheres $v_{r},v_{b},v_{g}$ each
with $\deg(v)+1$ boundary components. These punctured spheres correspond to
the three potential colors of $v$: red, blue, and green and we refer to them
as the _color surfaces_ of $v$. We glue $v_{r},v_{b},v_{g}$ to $\gamma_{v}$
each along some boundary component. For each edge $e=(u,v)$ we construct nine
tubes with two boundary components. Each tube connects a color surface of $u$
to a color surface of $v$, for example the tube $\mathcal{T}_{r,b}$ connects
the red color surface of $u$ with the blue color surface of $v$. We orient the
complex such that each 2-chain with boundary $\gamma$ and coefficients in
$\\{0,1\\}$ is an oriented manifold with boundary $\gamma$. For each tube
connecting two color surfaces of the same color (for example,
$\mathcal{T}_{r,r}$) we invert the orientation of one simplex, such that any
bounding chain for $\gamma$ including the inverted simplex will have to assign
it a coefficient of -1.

Any 2-chain with boundary $\gamma$ and coefficients in $\\{0,1\\}$ is a
surface as for each vertex it must contain exactly one color surface and for
each edge it must contain exactly one tube. Moreover, if any tube connecting
two color surfaces of the same color is contained in the solution it must
contain some simplex a negative coefficient and is not an directed
$\gamma$-path. It follows that $G$ is 3-colorable if and only if there is some
directed $\gamma$-path. ∎