#  Finding minimum bounded and homologous chains in simplicial complexes with
bounded-treewidth 1-skeleton

Mitchell Black School of Electrical Engineering and Computer Science, Oregon
State University<EMAIL_ADDRESS>.  Amir Nayyeri  School of
Electrical Engineering and Computer Science, Oregon State University;
<EMAIL_ADDRESS>.

###### Abstract

We consider two problems on simplicial complexes: the Optimal Bounded Chain
Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain
Problem asks to find the minimum weight $d$-chain in a simplicial complex $K$
bounded by a given $(d{-}1)$-chain, if such a $d$-chain exists. The Optimal
Homologous Chain problem asks to find the minimum weight $(d{-}1)$-chain in
$K$ homologous to a given $(d{-}1)$-chain. Both of these problems are NP-hard
and hard to approximate within any constant factor assuming the Unique Games
Conjecture. We prove that these problems are fixed-parameter tractable with
respect to the treewidth of the 1-skeleton of $K$.

##  1 Introduction

We consider two problems in this paper: the Optimal Bounded Chain Problem and
the Optimal Homologous Chain Problem. Both of these problems are NP-hard [16,
22], so it is natural to ask whether more efficient algorithms exist for any
special family of simplicial complexes. In this paper, we study algorithms for
these problems for simplicial complexes with bounded-width tree decompositions
of their 1-skeletons.

Tree decompositions have been used successfully to design algorithms on
graphs; see [18]. Often, graphs with tree decompositions of bounded-width
admit polynomial-time solutions to otherwise hard problems. Recently, tree
decompositions have also begun to be used for algorithms on simplicial
complexes. Existing algorithms use tree decompositions of a variety of graphs
associated with a simplicial complex. The most commonly used graph is the dual
graph of combinatorial $d$-manifolds [3, 8, 9, 10]. Other graphs that have
been used are the incidence graph between the $d$ and $(d+1)$-simplices
(a.k.a. level $d$ of the Hasse diagram) [9, 5, 4], the adjacency graph of the
$d$-simplices [5], and the 1-skeleton [3].

Our algorithms use a tree decomposition of the 1-skeleton. We observe that any
simplex of a simplicial complex will necessarily be contained in some bag of a
tree decomposition of its 1-skeleton. This is analogous to the requirement
that each vertex and edge of a graph be contained in some bag of a tree
decomposition. In this way, a tree decomposition of the 1-skeleton of a
simplicial complex is analogous to a tree decomposition of a graph.

The problems we consider ask to find a chain in a simplicial complex with
certain properties. There can be exponentially many such chains, so we cannot
simply check whether each chain or subcomplex has the desired property. Our
approach is to incrementally build these chains, checking along the way that
they have the desired property. Tree decompositions of the 1-skeleton of a
simplicial complex define a recursive structure on a simplicial complex that
we use to incrementally build our solutions.

###  1.1 Our Results

We now summarize the main results of our paper. Throughout, $n$ is the number
of vertices in the input simplicial complex and $k$ is the treewidth of the
1-skeleton of the input simplicial complex. Formal definitions of the terms
used will be given in Section 3.

The Optimal Bounded Chain Problem (OBCP) asks to find the minimum weight
$d$-chain $c$ of a simplicial complex $K$ bounded by a given $(d{-}1)$-chain
$b$, if such a chain $c$ exists. We work with chain groups with coefficients
in $\mathbb{Z}_{2}$, so a $d$-chain can therefore be thought of as a set of
$d$-simplices. The weight of a $d$-chain is the number of $d$-simplices it
contains. We show that OBCP is fixed-parameter tractable with respect to the
treewidth of the $1$-skeleton.

######  Theorem 1.1.

OBCP can be solved in $2^{O\left(k^{d}\right)}n\subset
2^{O\left(k^{k}\right)}n$ time.

As a corollary, our algorithm for OBCP can determine whether or not two
$(d{-}1)$-chains $b$ and $h$ are homologous. The naive algorithm for this
problem is to solve the system of linear equation $\partial c=b+h$ for $c$,
which takes $O(n^{\omega})$ time. Our algorithm runs in linear time on a
bounded-treewidth simplicial complex.

######  Corollary 1.2.

We can determine whether two $(d{-}1)$-chains are homologous in
$2^{O\left(k^{d}\right)}n\subset 2^{O\left(k^{k}\right)}n$ time.

The Optimal Homologous Chain Problem (OHCP) asks to find the minimal weight
$(d{-}1)$-chain $h$ homologous to a given $(d{-}1)$-chain $b$. If the chains
$b$ and $h$ are cycles, OHCP is also known as Homology Localization. We show
that OHCP is fixed-parameter tractable algorithm with respect to the treewidth
of the $1$-skeleton.

######  Theorem 1.3.

OHCP can be solved in $2^{O\left(k^{d}\right)}n\subset
2^{O\left(k^{k}\right)}n$ time.

Our results for OBCP and OHCP easily generalize to weighted complexes. We
discuss this at the end of Section 5.

##  2 Related Work

Blaser and Vȧgset [5] and Blaser et al. [4] independently discovered
treewidth-parameterized algorithms for OHCP and OBCP concurrently to this
paper. Their algorithms uses different graphs of the simplicial complex: the
adjacency graph of the $d$-simplices and the incidence graph of the
$(d{-}1)$\- and $d$-simplices. Our algorithms differ in the specifics but use
the same general strategy: use the tree decomposition to iteratively build the
homologous or bounded chains. While the algorithms have seemingly different
running times ($2^{O(k^{d})}n$ for ours, $O(2^{2k}n)$ for theirs), the
parameter $k$ is the treewidth of different graphs associated with a
simplicial complex, so it is not obvious how the runtimes of algorithms
compare. In Section 7, we compare the treewidth of these graphs and find that
in some cases the algorithms have comparable running times.

For the rest of this section, we will review the other previous work on the
problems OBCP and OHCP.

##### OBCP.

Dunfield and Hirani showed that OBCP is NP-hard [22]. Borradaile, Maxwell, and
Nayyeri showed OBCP over coefficients in $\mathbb{Z}_{2}$ is hard to
approximate within some constant factor if $P\neq NP$ and hard to approximate
with any constant factor assuming the Unique Games Conjecture, even for
embedded complexes [7]. Blaser et al. showed that OBCP is W[1]-hard when
parameterized by solution size [4].

On the positive side, there are algorithms to solve OBCP in embedded complexes
[7], $d$-manifolds [12], with coefficients in $\mathbb{R}$ [14], in special
cases with coefficients in $\mathbb{Z}$ [22], and with norms other than the
Hamming norm [17].

Our algorithm for OBCP can also be used to test whether two chains are
homologous and whether a cycle is null-homologous. The naive algorithm for
both of these problems is to solve a system of linear equations. Dey gives
algorithms to test whether a cycle embedded on a surface is null-homologous
that runs in $O(n+l)$ time, where $l$ is the length of the cycle, or with a
$O(n)$ time preprocessing step, $O(g+l)$ time, where $g$ is the genus of the
surface [19]. There is an algorithm for testing the homology class of a cycle
that runs in $O(gl)$ time with a $O(n^{\omega})$ preprocessing step, where $g$
is the rank of the homology group and $l$ is the number of simplices in the
cycle [11].

##### OHCP and Homology Localization.

Homology Localization is a special case of OHCP where the input chain is a
cycle; thus, hardness results for homology localization hold for OHCP as well.
Chen and Freedman showed that Homology Localization over coefficients in
$\mathbb{Z}_{2}$ is NP-hard to approximate within any constant factor [16].
Chambers, Erickson, and Nayyeri showed that Homology Localization is NP-hard
even for surface-embedded graphs [13]. Borradaile, Maxwell, and Nayyeri showed
that OHCP is hard to approximate within any constant factor assuming the
Unique Games Conjecture, even for embedded complexes [7]. Blaser and Vȧgset
showed Homology Localization is $W[1]$-hard when parameterized by solution
size [5].

On the positive side, there are parameterized algorithms to solve homology
localization for 1-cycles in surface embedded graphs [13, 23], 1-cycles in
simplicial complexes [11], and to solve OHCP in $(d{+}1)$-manifolds [7]. There
is an algorithm to solve OHCP with a norm other than the Hamming norm [17].
There are also linear programming based approaches to solve OHCP in special
cases with coefficients in $\mathbb{Z}$ [20].

##  3 Background

In this section, we present the mathematical background needed for the rest of
this paper.

###  3.1 Simplicial complexes

A simplicial complex is a set $K$ such that (1) each element $\sigma\in K$ is
a finite set and (2) for each $\sigma\in K$, if $\tau\subset\sigma$, then
$\tau\in K$. An element $\sigma\in K$ is a simplex. A simplex $\tau$ is a face
of a simplex $\sigma$ if $\tau\subset\sigma$. Likewise, $\sigma$ is a coface
of $\tau$. The simplices $\sigma$ and $\tau$ are incident.

A simplex $\sigma$ with $|\sigma|=d+1$ is a d-simplex. The set of all
$d$-simplices in $K$ is denoted $K_{d}$. The d-skeleton of $K$ is
$K^{d}=\cup_{i=0}^{d}K_{d}$. In particular, the 1-skeleton of $K$ is a graph.
The dimension of a simplicial complex is the largest integer $d$ such that $K$
contains a $d$-simplex.

The union $V=\cup_{\sigma\in K}\sigma$ is the set of vertices of a simplicial
complex. Each simplex in $K$ is a subset of $V$. A subset of vertices
$U\subset V$ defines a subcomplex of $K$. The subcomplex induced by U is
$K[U]=\\{\sigma\in K\,|\,\sigma\subset U\\}$.

###  3.2 Homology

Let $K$ be a simplicial complex. The dth chain group $C_{d}(K)$ of $K$ is the
free abelian group with coefficients over $\mathbb{Z}_{2}$ generated by
$K_{d}$. An element $\gamma\in C_{d}(K)$ is a d-chain. A $d$-chain $\gamma$
with coefficients over $\mathbb{Z}_{2}$ naturally corresponds to a set of
$d$-simplices in $K$, where the set contains a $d$-simplex $\sigma$ if and
only if the coefficient on $\sigma$ is 1. We overload notation and use
$\gamma$ to also refer to both the chain and the set defined by the chain. The
weight of a chain $\gamma$ is the number of simplices the set $\gamma$
contains and is denote $\|\gamma\|$; alternatively, $\|\gamma\|$ is the
Hamming norm of $\gamma$. Addition of two $d$-chains takes the symmetric
difference of the sets corresponding to these chains.

Let $\sigma$ be a $d$-simplex. The boundary of $\sigma$ is the $(d-1)$-chain
$\partial\sigma=\sum_{v\in\sigma}\sigma\setminus\\{v\\}.$ The boundary map
linearly extends the notion of boundary from $d$-simplices to $d$-chains. The
boundary map is the homomorphism $\partial_{d}:C_{d}(K)\to C_{d{-}1}(K)$ such
that $\partial_{d}\gamma=\sum_{\sigma\in\gamma}\partial\sigma$. When obvious,
we drop the $d$ and simply write $\partial_{d}$ as $\partial$. A
($d{-}1$)-chain $\beta$ bounds a $d$-chain $\gamma$ if $\partial\gamma=\beta$,
and the chain $\gamma$ spans $\beta$.

The composition of boundary maps $\partial_{d{-}1}\circ\partial_{d}=0$, the
zero map. As $C_{d}(K)$ is abelian, then
$\text{im}\,\partial_{d}\subset\ker\partial_{d{-}1}$ is a normal subgroup. The
(d-1)st homology group is the quotient group
$H_{d{-}1}(K)=\ker\partial_{d{-}1}/\text{im}\,\partial_{d}$. An element
$\beta\in\ker\partial_{d{-}1}$ is a (d-1)-cycle. A $(d{-}1)$-cycle $\beta$ is
null-homologous if $\beta=\partial\gamma$ for some $d$-chain $\gamma$. Two
$(d{-}1)$-chains $b$ and $h$ are homologous if $b+h$ is null-homologous.

###  3.3 Tree decompositions

Let $G=(V,E)$ be a graph. A tree decomposition of $G$ is a tuple $(T,X)$,
where $T=(I,F)$ is a tree with nodes $I$ and edges $F$, and $X=\\{X_{t}\subset
V\,|\,t\in I\\}$ such that (1) $\cup_{t\in I}X_{t}=V$, (2) for any
$\\{v_{1},v_{2}\\}\in E$, $\\{v_{1},v_{2}\\}\subset X_{t}$ for some $t\in I$,
and (3) for any $v\in V$, the subtree of $T$ induced by the nodes $\\{t\in
I\mid v\in X_{t}\\}$ is connected. A set $X_{t}$ is the bag of T. The width of
$(T,X)$ is ${\max}_{t\in I}|X_{t}|+1$. The treewidth of a graph $G$ is
$\operatorname{tw}(G)$, the minimum width of any tree decomposition of $G$.
Computing the treewidth of a graph is NP-hard [1], but there are algorithms to
compute tree decompositions that are within a constant factor of the
treewidth, e.g. see [6].

A nice tree decomposition is a tree decomposition with a specified root $r\in
I$ such that (1) $X_{r}=\emptyset$, (2) $X_{l}=\emptyset$ for all leaves $l\in
I$, and (3) all non-leaf nodes are either an introduce node, a forget node, or
a join node, which are defined as follows. An introduce node is a node $t\in
I$ with exactly one child $t^{\prime}$ such that for some $w\in V$, $w\notin
X_{t^{\prime}}$ and $X_{t}=X_{t^{\prime}}\cup\\{w\\}$. We say $t$ introduces
$w$. A forget node is a node $t\in I$ with exactly one child $t^{\prime}$ such
that for some $w\in V$, $w\notin X_{t}$ and $X_{t}\cup\\{w\\}=X_{t^{\prime}}$.
We say $t$ forgets $w$. A join node is a node $t\in I$ with two children
$t^{\prime},t^{\prime\prime}$ such that
$X_{t}=X_{t^{\prime}}=X_{t^{\prime\prime}}$.

######  Lemma 3.1 (Lemma 7.4 of [18]).

Given a tree decomposition $(T,X)$ of width $k$ of a graph $G=(V,E)$, a nice
tree decomposition of width $k$ with $O(kn)$ nodes can be computed in
$O(k^{2}\max\\{|V|,|I|\\})$ time.

Figure 1: Left: A simplicial complex. Right and Center: A (not nice) tree
decomposition of the simplicial complex. Each node of the tree corresponds to
a subset of the vertices of the simplicial complex

Let $K$ be a simplicial complex. Let $(T,X)$ be a tree decomposition of the
1-skeleton of $K$. Each vertex and edge of $K$ is contained in a bag of the
tree decomposition by definition. In general, all simplices of $K$ are
contained in a bag of the tree decomposition, which we prove in Corollary 3.3.

######  Lemma 3.2.

Let $(T,X)$ be a tree decomposition of a graph $G=(V,E)$. If $Q\subset V$
forms a clique in $G$, then there is a node $t\in I$ such that $Q\subset
X_{t}$. Moreover, the set of nodes $\\{t\in I\,|\,Q\subset X_{t}\\}$ form a
connected subtree of $T$.

###### Proof.

A proof that $Q$ is contained in $X_{t}$ for some node $t$ can be found in
[21, Lemma 12.3.5]. For the second claim, let $t_{1}$ and $t_{2}$ be nodes
such $Q\subset X_{t_{1}}\cap X_{t_{2}}$. Let $t_{3}$ be a node on the unique
path connecting $t_{1}$ and $t_{2}$. For any vertex $v\in Q$, $v\in X_{t_{3}}$
as $v\in X_{t_{1}}\cap X_{t_{2}}$ and the set of nodes whose bags contain $v$
form a connected subtree of $T$. So $Q\subset X_{t_{3}}$. ∎

######  Corollary 3.3.

Let $(T,X)$ be a tree decomposition of the 1-skeleton $K^{1}$ of a simplicial
complex $K$. Let $\sigma\in K$ be a simplex. There is a node $t\in I$ such
that $\sigma\subset X_{t}$. Moreover, the set of nodes $\\{t\in
I\,|\,\sigma\subset X_{t}\\}$ form a connected subtree of $T$.

###### Proof.

All subsets of $\sigma$ are simplices in $K$. In particular, for any vertices
$u,v\in\sigma$, the edge $\\{u,v\\}\in K$. Viewed as a set of vertices,
$\sigma$ forms a clique in $K^{1}$. ∎

As all simplices of $K$ are contained in some bag in the tree decomposition,
then the dimension of $K$ gives a lower bound on the treewidth of the
1-skeleton.

######  Corollary 3.4.

Let $K$ be a $d$-dimensional simplicial complex. Then
$\operatorname{tw}(K^{1})\geq d$.

In light of Corollary 3.3, we define a tree decomposition of a simplicial
complex K as a tree decomposition of the 1-skeleton of $K$. See Figure 1. The
terms nice tree decomposition, width of a tree decomposition, and treewidth of
a simplicial complex are all defined analogously.

##  4 The Generic Algorithm

In this section, we present a generic version of the algorithm for our two
problems. Later sections discuss the specific algorithms for each problem.

A tree decomposition $(T,X)$ of a simplicial complex $K$ defines a recursively
nested series of subcomplexes of the complex. We can use this series of
subcomplexes to recursively build solutions to our problems.

Specifically, subtrees of the tree $T$ define subcomplexes of $K$. For a node
$t$ in the tree, let $V_{t}$ be the union of the bags of each of $t$’s
descendants, including $t$ itself. If $K$ is a $d$-dimensional simplicial
complex, we define the subcomplex rooted at t to be
$K_{t}:=K[V_{t}]\setminus(K[X_{t}])_{d}$. See Figure 2. If $t^{\prime}$ is a
descendant of $t$, then $K_{t^{\prime}}\subset K_{t}$. We can therefore
recurse onto subcomplexes of $K$ by recursing onto subtrees $T$.

Figure 2: Right: A subtree rooted at $t$. Left: the corresponding subcomplex
$K_{t}$.

Each of our algorithms compute a set of candidate solutions at each node $t$.
The exact definition of candidate solution varies between problems, but
intuitively, a candidate solution at a node $t$ is a $d$-chain in $K_{t}$ that
could be a subset of an optimal solution. In each of our algorithms, we are
able to define our candidate solutions recursively: if $\gamma$ is a candidate
solution at $t$, then for each child $t^{\prime}$ of $t$, $\gamma\cap
K_{t^{\prime}}$ is a candidate solution at $t^{\prime}$. This is the key fact
our algorithm uses to find candidate solutions at $t$. Our algorithm attempts
to build candidate solutions at $t$ by adding $d$-simplices in $K_{t}\setminus
K_{t^{\prime}}$ to candidate solutions at $t^{\prime}$.

We compute the set of candidate solutions at the nodes in a bottom-up fashion,
starting at the leaves and moving towards the root. Our general approach for
computing the set of candidate solutions at $t$ is as follows. Take one
candidate solution from each of $t$’s children. Take the union of these
candidate solutions. Add a subset of $d$-simplices in $K_{t}$ that are not in
$K_{t^{\prime}}$ for any of $t$’s children $t^{\prime}$ to this union. Check
if this union is a candidate solution at $t$. Repeat for all sets of candidate
solutions at the children and all subset of $d$-simplices.

The above algorithm for computing the set of candidate solutions at a node is
generally correct, but because we use a nice tree decomposition, we won’t
perform every step of this algorithm at any one node. Instead, certain steps
of the algorithm are performed only at specialized nodes. For example, we only
take the union of candidate solutions from multiple children at join nodes, as
join nodes are the only type of node with multiple children. Also, we only add
a subset of $d$-simplices in $K_{t}\setminus K_{t^{\prime}}$ to the candidate
solutions at forget nodes.

It might be counter-intuitive that forgetting a vertex adds $d$-simplices to
$K_{t}$, so let’s see why this is the case. Let $t$ be a forget node and
$t^{\prime}$ its unique child. The set of vertices $V_{t}=V_{t^{\prime}}$, so
$K[V_{t}]=K[V_{t^{\prime}}]$. However, as the bags $X_{t^{\prime}}\subsetneq
X_{t}$, there may be $d$-simplices in $K[X_{t^{\prime}}]$ that are not in
$K[X_{t}]$. As we exclude the $d$-simplices in $K[X_{t^{\prime}}]$ from
$K_{t^{\prime}}$, the $d$-simplices in $K[X_{t^{\prime}}]\setminus K[X_{t}]$
will be in $K_{t}$ but not $K_{t^{\prime}}$. See Figure 3. Alternatively, for
introduce and join nodes, no new $d$-simplices are added to $K_{t}$ that do
not appear in some $K_{t^{\prime}}$ for a child $t^{\prime}$ of $t$. If $t$ is
an introduce node and $t^{\prime}$ is its unique child, we can prove
$(K_{t})_{d}=(K_{t^{\prime}})_{d}$. While introducing a vertex $v$ may add
$d$-simplices to $K[V_{t}]$, we can prove these simplices are always contained
in $K[X_{t}]$; see Lemma 5.3. Similarly, if $t$ is a join node and
$t^{\prime}$ and $t^{\prime\prime}$ are its two children, we can prove that
$(K_{t})_{d}=(K_{t^{\prime}})_{d}\sqcup(K_{t^{\prime\prime}})_{d}$; see Lemma
5.12.

Figure 3: An example of a forget node $t$ and its child $t^{\prime}$. The
triangle $\\{u,v,w\\}$ is contained in $K[X_{t^{\prime}}]$ but not $K[X_{t}]$.
As $K_{t}$ excludes triangles in $K[X_{t}]$, then $\\{u,v,w\\}\in
K_{t}\setminus K_{t^{\prime}}$.

##  5 Optimal Bounded Chain Problem

Let $K$ be a simplicial complex and $b\in C_{d{-}1}(K)$ a $(d{-}1)$-chain. The
Optimal Bounded Chain Problem asks to find the minimum weight $d$-chain $c\in
C_{d}(K)$ bounded by $b$, if such a chain $c$ exists. Let $(T,X)$ a nice tree
decomposition of $K$ with root $r$. We will use a dynamic program on $T$ to
compute $c$.

At a node $t\in T$, we are interested in the portion of $b$ contained in
$K_{t}$; we define the partial boundary at t as $b_{t}:=b\cap(K_{t}\setminus
K[X_{t}])$. Our key observation is that any $d$-simplex that is incident to
$b_{t}$ is contained in $K_{t}$. This means that after the iteration in the
algorithm where we process $t$, the portion of a candidate solution’s boundary
in $K_{t}$ but outside of $K[X_{t}]$ cannot be changed by adding more
$d$-simplices. Therefore, a candidate solution $\gamma$ at $t$ should be a
$d$-chain in $K_{t}$ that satisfies $\partial\gamma\setminus K[X_{t}]=b_{t}$.
Otherwise, we place no restriction on the rest of $\gamma$’s boundary,
$\partial\gamma\cap K[X_{t}]$. There might be other simplices in $K\setminus
K_{t}$ incident to $\partial\gamma\cap K[X_{t}]$, so even if
$\partial\gamma\cap K[X_{t}]\neq b\cap K[X_{t}]$, this portion of
$\partial\gamma$ might change later in the algorithm. We therefore let
$\partial\gamma\cap K[X_{t}]$ be any $(d{-}1)$-chain of $K[X_{t}]$. We call
this chain $\beta=\partial\gamma\cap K[X_{t}]$. A $d$-chain $\gamma\in
C_{d}(K_{t})$ is said to span $\boldsymbol{\beta}$ at t if
$\partial\gamma\setminus K[X_{t}]=b_{t}$ and $\partial\gamma\cap
K[X_{t}]=\beta$. See Figure 4.

Figure 4: Two examples of candidate solutions for OBCP. Notice that
$\partial\gamma\cap K[X_{t}]=\beta$ is different for the two candidate
solutions, but $\partial\gamma\setminus K[X_{t}]=b_{t}$ is the same. In
general, $\partial\gamma\cap K[X_{t}]$ can be any $(d{-}1)$-chain in
$K[X_{t}]$, but $\partial\gamma\setminus K[X_{t}]$ must be $b_{t}$.

For each $(d{-}1)$-chain $\beta$ in $K[X_{t}]$ such that $\beta\cup b_{t}$ is
a boundary cycle, we store the minimum weight of a $d$-chain that spans
$\beta$ at $t$ in the dynamic programming table entry $\mathbf{V}[\beta,t]$.
The bounded width of the decomposition implies a bounded number of
$(d{-}1)$-chains in $K[X_{t}]$, so the table $\mathbf{V}$ is of bounded size.
Lemma 5.1 tells us that the table $\mathbf{V}$ contains the weight of the
optimal solution.

######  Lemma 5.1.

The entry $\mathbf{V}[\emptyset,r]$ is the weight of the minimum weight chain
$c$ such that $\partial c=b$, if such a chain $c$ exists.

###### Proof.

Recall that the bag $X_{r}$ of the root $r$ in our tree decomposition is
empty, so $K[X_{r}]=\emptyset$. Also, each node in the tree decomposition is a
descendant of $r$, so $V_{r}=V$, $K_{r}=K$, and $b_{r}=b$. There is a unique
$(d{-}1)$-chain $\emptyset\in C_{d{-}1}(K[X_{r}])$. The entry
$\mathbf{V}[\emptyset,r]$ is the minimum weight of a $d$-chain $c\in
C_{d}(K_{r})=C_{d}(K)$ such that (1) $\partial c\cap X_{r}=\emptyset$ and,
more importantly, (2) $\partial c\setminus K[X_{r}]=\partial c=b_{r}=b$. If no
such chain $c$ exists, then $\mathbf{V}[\emptyset,r]=\infty$. ∎

We are almost ready to present our algorithm for OBCP, but first, we need a
lemma.

######  Lemma 5.2.

If $\sigma\in K[V_{t}]$, then there is a descendant $t_{\sigma}$ of $t$ such
that $\sigma\in K[X_{t_{\sigma}}]$. In particular, if $\sigma\in K[V_{t}]$,
then there is a descendant $t_{\sigma}$ of $t$ such that $\sigma\in
K[X_{t_{\sigma}}]$

###### Proof.

Recall that $K_{t}=K[V_{t}]\setminus(K[X_{t}])_{d}$, so $K_{t}\subset
K[V_{t}]$. We prove the more general statement that if $\sigma\in K[V_{t}]$,
then there is a descendant $t_{\sigma}$ of $t$ such that $\sigma\in
K[X_{t_{\sigma}}]$. Let $\sigma\in K[V_{t}]$. By Lemma 3.2 there is a node
$t_{\sigma}$ in $T$ such that $\sigma\subset X_{t_{\sigma}}$. If $t_{\sigma}$
is in the subtree rooted at $t$, we are done. So assume $t_{\sigma}$ is not in
the subtree rooted at $t$. For every $v\in\sigma$, there is a node $t_{v}$ in
the subtree rooted at $t$ such that $v\in X_{t_{v}}$. As well, $v\in
X_{t_{\sigma}}$ as $v\in\sigma\subset X_{t_{\sigma}}$. The nodes containing
$v$ form a connected subtree of $T$. So $v$ is contained in the bag of each
node on the unique path connecting $t_{v}$ and $t_{\sigma}$. In particular,
$v\in X_{t}$. Therefore, the bag $X_{t}$ contains every $v\in\sigma$, so
$\sigma\in K[X_{t}]$. ∎

We now give our dynamic program to compute $\mathbf{V}$ on a nice tree
decomposition. We compute the table $\mathbf{V}$ starting at the leaves of $T$
and moving towards the root. At each node $t$ in our tree decomposition, we
calculate the entries $\mathbf{V}[\beta,t]$ using the entries of $\mathbf{V}$
of $t$’s children. Therefore, to specify our dynamic program, it suffices to
specify how to calculate $\mathbf{V}$ at each type of node in a nice tree
decomposition.

###  5.1 Leaf Nodes

Let $t$ be a leaf node. Recall that $X_{t}=\emptyset$, so
$K[X_{t}]=\emptyset$. Moreover, $t$ has no children, so
$V_{t}=K_{t}=b_{t}=\emptyset$. There is a unique $(d{-}1)$-chain
$\beta=\emptyset\in C_{d{-}1}(K[X_{t}])$. There is also a unique $d$-chain
$\gamma=\emptyset\in C_{d}(K_{t})$. The chain $\gamma$ spans $\beta$ at $t$,
so the unique table entry $\mathbf{V}[\emptyset,t]=0$.

###  5.2 Introduce Nodes

Let $t$ be an introduce node and $t^{\prime}$ the unique child of $t$. Recall
that $X_{t}=X_{t^{\prime}}\sqcup\\{w\\}$ for some vertex $w\in K$. Our first
observation is that any simplex in the subcomplex $K[V_{t}]$ that contains $w$
is only contained in the subcomplex at the bag $K[X_{t}]$.

######  Lemma 5.3.

Let $\sigma\in K[V_{t}]$ such that $w\in\sigma$. Then $\sigma\in
K[X_{t}]\setminus K[V_{t^{\prime}}]$.

###### Proof.

As $\sigma\in K[V_{t}]$, then by Lemma 5.2, there is a node $t_{\sigma}$ in
the subtree rooted at $t$ such that $\sigma\in K[X_{t_{\sigma}}]$. Suppose for
the purposes of contradiction that $t\neq t_{\sigma}$. Then $t_{\sigma}$ is in
the subtree rooted at $t^{\prime}$. As $w\in\sigma$, then $w\in
X_{t_{\sigma}}$. The set of nodes whose bags contain $w$ form a connected
subtree of $T$, so each node on the unique path connecting $t$ and
$t_{\sigma}$ must contain $w$ in its bag. The node $t^{\prime}$ is on this
path, but $w\notin X_{t^{\prime}}$, a contradiction. Thus, $t=t_{\sigma}$. As
no node in the subtree rooted at $t^{\prime}$ contains $\sigma$, then by Lemma
5.2, $\sigma\notin K[V_{t^{\prime}}]$. ∎

As each simplex that contains $w$ is contained in $K[X_{t}]$, then introducing
$w$ does not change the complexes $K_{t}$ outside of $K[X_{t}]$. We prove this
in the following lemma.

######  Lemma 5.4.

The complexes $K_{t^{\prime}}\setminus K[X_{t^{\prime}}]=K_{t}\setminus
K[X_{t}]$.

###### Proof.

Observe that $K_{t}\setminus
K[X_{t}]=(K[V_{t}]\setminus(K[X_{t}])_{d})\setminus K[X_{t}]=K[V_{t}]\setminus
K[X_{t}]$. We will therefore prove that $K[V_{t}]\setminus
K[X_{t}]=K[V_{t^{\prime}}]\setminus K[X_{t^{\prime}}]$.

Let $\sigma\in K[V_{t^{\prime}}]\setminus K[X_{t^{\prime}}]$. It follows that
$\sigma\in K[V_{t}]$ as $V_{t^{\prime}}\subset V_{t}$. We need to show that
$\sigma\notin K[X_{t}]$. Suppose $\sigma\in K[X_{t}]$. As $X_{t}\setminus
X_{t^{\prime}}=\\{w\\}$, then $w\in\sigma$. This cannot be the case, as any
simplex containing $w$ is not in $K_{t^{\prime}}\subset K[V_{t^{\prime}}]$ by
Lemma 5.3. So $\sigma\notin K[X_{t}]$ and $\sigma\in K_{t}\setminus K[X_{t}]$

Now let $\sigma\in K[V_{t}]\setminus K[X_{t}]$. We conclude that
$\sigma\not\in K[X_{t^{\prime}}]$ as $X_{t^{\prime}}\subset X_{t}$. We need to
show that $\sigma\in K[V_{t^{\prime}}]$. Suppose $\sigma\not\in
K[V_{t^{\prime}}]$. Each descendant of $t$ is a descendant of $t^{\prime}$
except $t$ itself. As $X_{t}\setminus X_{t^{\prime}}=\\{w\\}$, then
$V_{t}\setminus V_{t^{\prime}}$ can only contain $w$. We conclude
$w\in\sigma$. This is a contradiction, as any simplex containing $w$ in
$K_{t}$ is contained in $K[X_{t}]$ by Lemma 5.3. Thus $\sigma\in
K[V_{t^{\prime}}]\setminus K[X_{t^{\prime}}]$. ∎

As introducing $w$ does not change $K_{t}$ outside of the bag $X_{t}$, then
neither the chain group $C_{d}(K_{t})$ nor the partial boundary $b_{t}$ are
changed by introducing $w$. We prove this in the following two lemmas.

######  Lemma 5.5.

The chain groups $C_{d}(K_{t^{\prime}})=C_{d}(K_{t})$.

###### Proof.

We prove this by showing that $(K_{t^{\prime}})_{d}=(K_{t})_{d}$. This follows
from Lemma 5.4 as
$(K_{t})_{d}=(K[V_{t}]\setminus(K[X_{t}])_{d})_{d}=(K_{t}\setminus
K[X_{t}])_{d}$. ∎

######  Lemma 5.6.

The chain $b_{t}=b_{t^{\prime}}$.

###### Proof.

This follows from Lemma 5.4, as $b_{t}=b\cap K_{t}\setminus K[X_{t}]=b\cap
K_{t^{\prime}}\setminus K[X_{t^{\prime}}]=b_{t^{\prime}}.$ ∎

Introducing $w$ to the bag $X_{t}$ does not change $C_{d}(X_{t})$ or $b_{t}$,
so unsurprisingly, the values in the dynamic programming table don’t change
either. The following lemma proves this and gives a formula for computing
$\mathbf{V}[\beta,t]$.

######  Lemma 5.7.

Let $t$ be an introduce node and let $t^{\prime}$ be the unique child of $t$.
Let $\beta\in C_{d-1}(K[X_{t}])$. Then

$\mathbf{V}[\beta,t]=\begin{cases}\mathbf{V}[\beta,t^{\prime}]&\text{ if
}\beta\in C_{d{-}1}(K[X_{t^{\prime}}])\\\ \infty&\text{
otherwise.}\end{cases}$

###### Proof.

Let $\beta\in C_{d{-}1}(K[X_{t^{\prime}}])$. We claim that any chain
$\gamma\in C_{d}(K_{t^{\prime}})$ spanning $\beta$ at $t^{\prime}$ spans
$\beta$ at $t$ and vice versa. Let $\gamma$ be a $d$-chain that spans $\beta$
at $t^{\prime}$. As $C_{d}(K_{t^{\prime}})=C_{d}(K_{t})$, then $\gamma$ is a
$d$-chain in both $K_{t}$ and $K_{t^{\prime}}$; moreover,
$\partial\gamma\subset K_{t}\cap K_{t^{\prime}}$, so
$\partial\gamma=\partial\gamma\cap K_{t}=\partial\gamma\cap K_{t^{\prime}}$.
Using this fact and Lemma 5.4, we see

$\partial\gamma\setminus K[X_{t^{\prime}}]=(\partial\gamma\cap
K_{t^{\prime}})\setminus K[X_{t^{\prime}}]=(\partial\gamma\cap K_{t})\setminus
K[X_{t}]=\partial\gamma\setminus K[X_{t}].$

We use the fact that $\partial\gamma\cap K[X_{t^{\prime}}]=\partial\gamma\cap
K[X_{t}]$ to prove that $\partial\gamma\cap K[X_{t}]=b_{t}$. Indeed, as
$\partial\gamma\setminus K[X_{t^{\prime}}]=b_{t^{\prime}}$ and
$b_{t^{\prime}}=b_{t}$ from Lemma 5.6, then $\partial\gamma\setminus
K[X_{t}]=b_{t}$. Moreover, as $\partial\gamma=\beta\sqcup b_{t}$, then the
rest of the $\partial\gamma$ is $\partial\gamma\cap K[X_{t}]=\beta$. This
completes the proof that $\gamma$ spans $\beta$ at $t$. By the same argument,
any chain spanning $\beta$ at $t$ spans $\beta$ at $t^{\prime}$. As the same
set of chains span $\beta$ at $t$ and $t^{\prime}$, then
$\mathbf{V}[\beta,t]=\mathbf{V}[\beta,t^{\prime}]$

Now let $\beta\in C_{d{-}1}(K[X_{t}])\setminus C_{d{-}1}(K[X_{t^{\prime}}])$.
As $\beta\notin C_{d{-}1}(K[X_{t^{\prime}}])$, there must be a simplex
$\sigma\in\beta$ such that $w\in\sigma$. As any simplex $\sigma$ such that
$w\in\sigma$ is not contained in $K[X_{t^{\prime}}]$, there is no chain
$\gamma\in C_{d}(K_{t})$ that spans $\beta$ at $t$ as
$C_{d}(K_{t})=C_{d}(K_{t^{\prime}})$. Thus, $\mathbf{V}[\beta,t]=\infty$. ∎

###  5.3 Forget Nodes

Let $t$ be a forget node and $t^{\prime}$ the unique child of $t$. Recall that
$X_{t}\sqcup\\{w\\}=X_{t^{\prime}}$. Forget nodes add new chains to the chain
group $C_{d}(K_{t})$. In particular, any $d$-simplex
$\sigma\in(K[X_{t^{\prime}}])_{d}$ that contains $w$ is not contained in
$K_{t^{\prime}}$ but will be contained in $K_{t}$. We prove this in our first
lemma. Let
$(K[X_{t^{\prime}}])_{d}^{w}=\\{\sigma\in(K[X_{t^{\prime}}])_{d}\,|\,w\in\sigma\\}$
and let $C_{d}^{w}(K[X_{t^{\prime}}])$ be the free abelian group on
$(K[X_{t^{\prime}}])_{d}^{w}$ with coefficients in $\mathbb{Z}_{2}$.

######  Lemma 5.8.

The chain group $C_{d}(K_{t})=C_{d}(K_{t^{\prime}})\oplus
C_{d}^{w}(K[X_{t^{\prime}}])$.

###### Proof.

As $C_{d}(K_{t})$ is generated by $(K_{t})_{d}$, we can prove the lemma by
showing that
$(K_{t})_{d}=(K_{t^{\prime}})_{d}\sqcup(K[X_{t^{\prime}}])_{d}^{w}$.

We first prove that $(K_{t^{\prime}})_{d}\subset(K_{t})_{d}$. Let
$\sigma\in(K_{t^{\prime}})_{d}$. By the definition of $K_{t^{\prime}}$,
$\sigma\in K[V_{t^{\prime}}]$ and $\sigma\not\in K[X_{t^{\prime}}]$. We know
that $K[V_{t}]=K[V_{t^{\prime}}]$ as each descendant of $t^{\prime}$ is a
descendant of $t$ and $X_{t}\subset X_{t^{\prime}}$, so $\sigma\in K[V_{t}]$
as well. Furthermore, $\sigma\not\in K[X_{t}]$ as $K[X_{t}]\subset
K[X_{t^{\prime}}]$ and $\sigma\not\in K[X_{t^{\prime}}]$. As $\sigma\in
K[V_{t}]$ and $\sigma\not\in K[X_{t}]$, then $\sigma\in(K_{t})_{d}$ as
$(K_{t})_{d}=K[V_{t}]\setminus K[X_{t}]$. This proves that
$(K_{t^{\prime}})_{d}\subset(K_{t})_{d}$.

As $(K_{t^{\prime}})_{d}\subset(K_{t})_{d}$, the next step to proving
$(K_{t})_{d}=(K_{t^{\prime}})_{d}\sqcup(K[X_{t^{\prime}}])_{d}^{w}$ is to show
that $(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}=(K[X_{t^{\prime}}])_{d}^{w}$.
Let $\sigma\in(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}$. As
$\sigma\in(K_{t})_{d}$, then $\sigma\in K[V_{t}]$ and $\sigma\not\in
K[X_{t}]$. As $\sigma\notin(K_{t})_{d}$, then either $\sigma\not\in
K[V_{t^{\prime}}]$ or $\sigma\in K[X_{t^{\prime}}]$. We know that $\sigma\in
K[V_{t^{\prime}}]$, as we proved in the previous paragraph that
$K[V_{t^{\prime}}]=K[V_{t}]$, so we conclude that $\sigma\in
K[X_{t^{\prime}}]$. It must be the case that $w\in\sigma$ as $\sigma\in
K[X_{t^{\prime}}]\subset K[X_{t}]$ and $X_{t^{\prime}}\setminus
X_{t}=\\{w\\}$, so $\sigma\in(K[X_{t^{\prime}}])_{d}^{w}$. This proves that
$(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}\subset(K[X_{t^{\prime}}])_{d}^{w}$

We now prove that
$(K[X_{t^{\prime}}])_{d}^{w}\subset(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}$.
Let $\sigma\in(K[X_{t^{\prime}}])_{d}^{w}$. We know that $\sigma\in
K[X_{t^{\prime}}]$, which implies that $\sigma\in K[V_{t}]$ as
$K[X_{t^{\prime}}]\subset K[V_{t}]$. As $w\in\sigma$, we also have that
$\sigma\not\in K[X_{t}]$, so $\sigma\in(K_{t})_{d}$. Lastly, as
$\sigma\in(K[X_{t^{\prime}}])_{d}$, then
$\sigma\notin(K_{t^{\prime}})_{d}=K[V_{t^{\prime}}]\setminus
K[X_{t^{\prime}}]$. Thus, $\sigma\in(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}$
and
$(K[X_{t^{\prime}}])_{d}^{w}\subset(K_{t})_{d}\setminus(K_{t^{\prime}})_{d}$.
∎

Intuitively, we can build the chain $\gamma$ that attains
$\mathbf{V}[\beta,t]$ by composing a minimal chain $\gamma^{\prime}\in
C_{d}(K[X_{t^{\prime}}])$ that attains $V[\beta^{\prime},t^{\prime}]$ and a
chain $\gamma_{w}\in C_{d}^{w}(K[X_{t^{\prime}}])$ of $d$-simplices that all
contain $w$. We need to enforce that
$\partial(\gamma^{\prime}+\gamma_{w})=\beta+b_{t}$. The chain
$\gamma^{\prime}$ includes $b_{t^{\prime}}$ in the portion of its boundary
outside $K[X_{t^{\prime}}]$, so we want to choose $\gamma_{w}$ to help cover
the rest of the boundary $b_{t}\setminus b_{t^{\prime}}$. We can prove that
$b_{t}\setminus b_{t^{\prime}}$ is contained in $K[X_{t^{\prime}}]$, i.e.
$b_{t}\setminus b_{t^{\prime}}=b_{t}\cap K[X_{t^{\prime}}]$. So if
$(\partial(\gamma^{\prime}+\gamma_{w})\cap K[X_{t^{\prime}}])\setminus
K[X_{t}]=b_{t}\cap K[X_{t^{\prime}}]$, then
$\partial(\gamma^{\prime}+\gamma_{w})\setminus K[X_{t}]$ will cover all of
$b_{t}$. This is equivalently to requiring that
$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]=b_{t}\cap
K[X_{t^{\prime}}]$, as $\partial\gamma^{\prime}\cap K[X_{t}]=\beta^{\prime}$
and $\partial\gamma_{w}\cap K[X_{t}]=\gamma_{w}$. Indeed, this is the
requirement we see in the formula for $\mathbf{V}[\beta,t]$ in Lemma 5.10.

We first give a characterization of $b_{t^{\prime}}$.

######  Lemma 5.9.

The chain $b_{t^{\prime}}=b_{t}\setminus K[X_{t^{\prime}}].$

###### Proof.

The chains $b_{t}$ and $b_{t^{\prime}}$ are defined $b_{t^{\prime}}=(b\cap
K_{t^{\prime}})\setminus K[X_{t^{\prime}}]$ and $b_{t}=(b\cap K_{t})\setminus
K[X_{t}]$. If we consider the difference $b_{t}\setminus K[X_{t^{\prime}}]$,
we find that

$b_{t}\setminus K[X_{t^{\prime}}]=((b\cap K_{t})\setminus K[X_{t}])\setminus
K[X_{t^{\prime}}]=(b\cap K_{t})\setminus K[X_{t^{\prime}}]$

as $K[X_{t}]\subset K[X_{t^{\prime}}]$. We will use this fact later.

The sets of vertices in the trees rooted at $t$ and $t^{\prime}$ are equal,
i.e. $V_{t}=V_{t^{\prime}}$, but the vertices in the bags $X_{t}\subset
X_{t^{\prime}}$. We use these two facts to show that the complexes $K_{t}$ and
$K_{t^{\prime}}$ only differ in the complexes induced by their bags, namely
$K_{t}\setminus K[X_{t^{\prime}}]=K_{t^{\prime}}\setminus K[X_{t^{\prime}}]$:

$K_{t}\setminus K[X_{t^{\prime}}]=K[V_{t}]\setminus(K[X_{t}])_{d}\setminus
K[X_{t^{\prime}}]=K[V_{t}]\setminus
K[X_{t^{\prime}}]=K[V_{t^{\prime}}]\setminus(K[X_{t^{\prime}}])_{d}\setminus
K[X_{t^{\prime}}]=K_{t^{\prime}}\setminus K[X_{t^{\prime}}].$

We have proved that $b_{t}=b\cap(K_{t}\setminus K[X_{t^{\prime}}])$. We have
also proved that $K_{t}\setminus K[X_{t^{\prime}}]=K_{t^{\prime}}\setminus
K[X_{t^{\prime}}]$. We use these facts to prove that $b_{t}\setminus
K[X_{t^{\prime}}]=b_{t^{\prime}}$ as

$b_{t}\setminus K[X_{t^{\prime}}]=b\cap K_{t}\setminus K[X_{t^{\prime}}]=b\cap
K_{t^{\prime}}\setminus K[X_{t^{\prime}}]=b_{t^{\prime}}.\qed$

Lemma 5.9 implies that $b_{t}\setminus b_{t^{\prime}}=b_{t}\cap
K[X_{t^{\prime}}]$, as claimed above. We are now ready to give a formula for
$\mathbf{V}[\beta,t]$.

######  Lemma 5.10.

Let $\beta\in C_{d{-}1}(K[X_{t}])$. Then

$\mathbf{V}[\beta,t]=\underset{\beta^{\prime},\gamma_{w}}{\min}\;\mathbf{V}[\beta^{\prime},t^{\prime}]+\|\gamma_{w}\|$

where the minimization ranges over $\beta^{\prime}$ and $\gamma_{w}$ such that

  * •

$\beta^{\prime}\in C_{d{-}1}(K[X_{t^{\prime}}])$

  * •

$\gamma_{w}\in C_{d}^{w}(K[X_{t^{\prime}}])$

  * •

$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$

  * •

$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]=b_{t}\cap
K[X_{t^{\prime}}]$

###### Proof.

First, we show that each $d$-chain on the right hand side of the equation in
the lemma spans $\beta$ at $t.$ Let $\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$
that attains $\mathbf{V}[\beta^{\prime},t^{\prime}]$, and let $\gamma_{w}\in
C_{d}^{w}(K[X_{t^{\prime}}])$ such that
$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$ and
$(\beta+\partial\gamma_{w})\setminus K[X_{t}]=b_{t}\cap K[X_{t^{\prime}}]$ Let
$\gamma=\gamma^{\prime}+\gamma_{w}$; we show that $\gamma$ spans $\beta$ at
$t$. The boundary

$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}=b_{t^{\prime}}+\beta^{\prime}+\partial\gamma_{w}.$

If $\gamma$ were to span $\beta$ at $t$, then $\partial\gamma\cap
K[X_{t}]=\beta$ and $\partial\gamma\setminus K[X_{t}]=b_{t}$. The intersection
$\partial\gamma\cap K[X_{t}]$ is

$\displaystyle\partial\gamma\cap K[X_{t}]=$
$\displaystyle(b_{t^{\prime}}+\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]$
$\displaystyle=$ $\displaystyle(\beta^{\prime}+\partial\gamma_{w})\cap
K[X_{t}]$ (as $b_{t^{\prime}}\cap K[X_{t^{\prime}}]=\emptyset$)
$\displaystyle=$ $\displaystyle\beta$ (by assumption)

The difference $\partial\gamma\setminus K[X_{t}]$ is

$\displaystyle\partial\gamma\setminus K[X_{t}]=$
$\displaystyle(b_{t^{\prime}}+\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]$ $\displaystyle=$ $\displaystyle
b_{t^{\prime}}+(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]$ (as
$b_{t^{\prime}}\cap K[X_{t}]=\emptyset$) $\displaystyle=$ $\displaystyle
b_{t^{\prime}}+b_{t}\cap K[X_{t^{\prime}}]$ (by assumption) $\displaystyle=$
$\displaystyle b_{t}\setminus K[X_{t^{\prime}}]+b_{t}\cap K[X_{t^{\prime}}]$
(by Lemma 5.9) $\displaystyle=$ $\displaystyle b_{t}$

This proves that $\gamma$ indeed spans $\beta$ at $t$. Moreover, as
$\gamma^{\prime}$ and $\gamma_{w}$ are disjoint, then
$\|\gamma\|=\|\gamma^{\prime}\|+\|\gamma_{w}\|$. As $\gamma^{\prime}$ achieves
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ by assumption, then
$\|\gamma\|=\mathbf{V}[\beta^{\prime},t^{\prime}]+\|\gamma_{w}\|$.

Next, we verify that the chain that achieves $\mathbf{V}[\beta,t]$ is included
in the right hand side of the equation. By Lemma 5.8,
$\gamma=\gamma^{\prime}+\gamma_{w}$ for some $\gamma^{\prime}\in
C_{d}(K_{t^{\prime}})$ and $\gamma_{w}\in C_{d}^{w}(K[X_{t^{\prime}}])$. Let
$\beta^{\prime}=\partial\gamma^{\prime}\cap K[X_{t^{\prime}}]$. We need to
verify that $\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$ and
achieves $\mathbf{V}[\beta^{\prime},t^{\prime}]$, that
$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$, and that
$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]=b_{t}\cap
K[X_{t^{\prime}}]$.

We first prove that $\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$.
We already know that $\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]=\beta^{\prime}$, so we only need to prove that
$\partial\gamma^{\prime}\setminus K[X_{t^{\prime}}]=b_{t^{\prime}}$. Indeed,

$\displaystyle\partial\gamma^{\prime}\setminus K[X_{t^{\prime}}]=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma_{w})\setminus
K[X_{t^{\prime}}]$ (as $\partial\gamma_{w}\subset K[X_{t^{\prime}}]$)
$\displaystyle=$ $\displaystyle\partial\gamma\setminus K[X_{t^{\prime}}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}$) $\displaystyle=$
$\displaystyle(\beta+b_{t})\setminus K[X_{t^{\prime}}]$ (as $\gamma$ bounds
$\beta$ at $t$) $\displaystyle=$ $\displaystyle b_{t}\setminus
K[X_{t^{\prime}}]$ (as $\beta\subset K[X_{t}]$ and $K[X_{t}]\subset
K[X_{t^{\prime}}]$) $\displaystyle=$ $\displaystyle b_{t^{\prime}}$ (by Lemma
5.9)

This proves that $\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$. We
delay proving that $\gamma^{\prime}$ achieves
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ until the end of the proof.

We now prove that $(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$. We
see that

$\displaystyle\beta=$ $\displaystyle\partial\gamma\cap K[X_{t}]$ (by
assumption) $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma_{w})\cap K[X_{t}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}$) $\displaystyle=$
$\displaystyle(b_{t^{\prime}}+\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]$
(as $\gamma^{\prime}$ bounds $\beta^{\prime}$ at $t^{\prime}$)
$\displaystyle=$ $\displaystyle(\beta^{\prime}+\partial\gamma_{w})\cap
K[X_{t}]$ (as $b_{t^{\prime}}\cap K[X_{t}]=\emptyset$.)

Finally, we prove that $(\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]=b_{t}\cap K[X_{t^{\prime}}]$.

$\displaystyle b_{t}\cap K[X_{t^{\prime}}]=$
$\displaystyle(\partial\gamma\setminus K[X_{t}])\cap K[X_{t^{\prime}}]$ (as
$\gamma$ spans $\beta$ at $t$) $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]\cap K[X_{t^{\prime}}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}$) $\displaystyle=$
$\displaystyle(b_{t^{\prime}}+\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]\cap K[X_{t^{\prime}}]$ (as $\gamma^{\prime}$ bounds $\beta^{\prime}$
at $t^{\prime}$) $\displaystyle=$
$\displaystyle(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]$ (as
$b_{t^{\prime}}\cap K[X_{t^{\prime}}]=\emptyset$)

We are now ready to prove that $\gamma^{\prime}$ achieves
$\mathbf{V}[\beta^{\prime},t^{\prime}]$. Suppose not, and let
$\gamma^{\prime}_{o}\in C_{d}(K_{t^{\prime}})$ be a chain that achieves
$V[\beta^{\prime},t^{\prime}]$. We showed in the previous paragraph that
$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$ and
$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]=b_{t}\cap
K[X_{t^{\prime}}]$. This implies that $\gamma^{\prime}_{o}+\gamma_{w}$ spans
$\beta$ at $t$ by the first half of this proof. Moreover,
$\|\gamma^{\prime}_{o}+\gamma_{w}\|<\|\gamma^{\prime}+\gamma_{w}\|=\|\gamma\|$,
which contradicts the assumed optimality of $\gamma$. Thus, $\gamma^{\prime}$
achieves $V[\beta^{\prime},t^{\prime}]$ and $\gamma$ is included in the right
hand side of the equation. ∎

###  5.4 Join Nodes

Let $t$ be a join node, and let $t^{\prime}$ and $t^{\prime\prime}$ be the two
children of $t$. Recall that $X_{t}=X_{t^{\prime}}=X_{t^{\prime\prime}}$. We
first observe that $K_{t^{\prime}}$ and $K_{t^{\prime\prime}}$ only overlap in
$K[X_{t}]$.

######  Lemma 5.11.

The complex $K_{t}\setminus K[X_{t}]=(K_{t^{\prime}}\setminus
K[X_{t}^{\prime}])\sqcup(K_{t^{\prime\prime}}\setminus
K[X_{t^{\prime\prime}}]).$

###### Proof.

As $K[X_{t}]=K[X_{t^{\prime}}]=K[X_{t^{\prime\prime}}]$, we see immediately
that both $K_{t^{\prime}}\setminus K[X_{t^{\prime}}]\subset K_{t}\setminus
K[X_{t}]$ and $K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]\subset
K_{t}\setminus K[X_{t}]$ as both $K_{t^{\prime}}\subset K_{t}$ and
$K_{t^{\prime\prime}}\subset K_{t}$.

We now prove that $K_{t^{\prime}}\setminus K[X_{t^{\prime}}]$ and
$K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]$ are disjoint. Suppose
there is a simplex $\sigma\in(K_{t^{\prime}}\setminus
K[X_{t^{\prime}}])\cap(K_{t^{\prime\prime}}\setminus
K[X_{t^{\prime\prime}}])$. Then by Lemma 5.2, there are nodes
$t_{\sigma}^{\prime}$ and $t_{\sigma}^{\prime\prime}$ in the subtrees rooted
at $t^{\prime}$ and $t^{\prime\prime}$ such that $\sigma\in
K[X_{t_{\sigma}^{\prime}}]$ and $\sigma\in K[X_{t_{\sigma}^{\prime\prime}}]$.
The set of nodes containing $\sigma$ form a connected subtree. This is a
contradiction, as $t$ lies on the unique path connecting $t_{\sigma}^{\prime}$
and $t_{\sigma}^{\prime\prime}$ and $\sigma\notin K[X_{t}]$ by assumption.
Hence $K_{t^{\prime}}\setminus K[X_{t^{\prime\prime}}]\cap
K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]=\emptyset$.

We now prove that $K_{t}\setminus K[X_{t}]\subset(K_{t^{\prime}}\setminus
K[X_{t^{\prime}}])\sqcup(K_{t^{\prime\prime}}\setminus
K[X_{t^{\prime\prime}}])$. Let $\sigma\in K_{t}\setminus K[X_{t}]$. By Lemma
5.2, there is a node $t_{\sigma}$ in the subtree rooted at $t$ such that
$\sigma\in K[X_{t_{\sigma}}]$. We know $t_{\sigma}\neq t$ as $\sigma\notin
K[X_{t}]$, so $t_{\sigma}$ is either in the subtree rooted at $t^{\prime}$ or
the subtree rooted at $t^{\prime\prime}$. ∎

Lemma 5.11 implies that any $d$-chain in $K_{t}$ is the sum of a $d$-chain in
$K_{t^{\prime}}$ and a $d$-chain in $K_{t^{\prime\prime}}$. We prove this in
the following lemma.

######  Lemma 5.12.

The chain group $C_{d}(K_{t})=C_{d}(K_{t^{\prime}})\oplus
C_{d}(K_{t^{\prime\prime}})$.

###### Proof.

As $C_{d}(K_{t})$ is generated by $(K_{t})_{d}$, we can prove this by showing
that $(K_{t})_{d}=(K_{t^{\prime}})_{d}\sqcup(K_{t^{\prime\prime}})_{d}$. We
first note that

$(K_{t})_{d}=(K[V_{t}]\setminus(K[X_{t}])_{d})_{d}=(K[V_{t}]\setminus
K[X_{t}])_{d}$

so it follows by Lemma 5.11 that

$(K_{t})_{d}=(K[V_{t}]\setminus K[X_{t}])_{d}=(K[V_{t^{\prime}}]\setminus
K[X_{t^{\prime}}])_{d}\sqcup(K[V_{t^{\prime\prime}}]\setminus
K[X_{t^{\prime\prime}}])_{d}=(K_{t^{\prime}})_{d}\sqcup(K_{t^{\prime\prime}})_{d}.\qed$

Similarly, the boundary $b_{t}$ is composed of a portion in $K_{t^{\prime}}$,
namely $b_{t^{\prime}}$, and a portion in $K_{t^{\prime\prime}}$, namely
$b_{t^{\prime\prime}}$.

######  Corollary 5.13.

The chain $b_{t}=b_{t^{\prime}}\sqcup b_{t^{\prime\prime}}.$

###### Proof.

The boundary $b_{t}=b\cap K_{t}\setminus K[X_{t}]$. Using Lemma 5.11,

$b_{t}=b\cap K_{t}\setminus K[X_{t}]=(b\cap K_{t^{\prime}}\setminus
K[X_{t}])\sqcup(b\cap K_{t^{\prime\prime}}\setminus
K[X_{t}])=b_{t^{\prime}}\sqcup b_{t^{\prime\prime}}.\qed$

These two lemmas tell us that a chain $\gamma$ that spans $\beta$ at $t$ is
the sum of chains $\gamma^{\prime}$ and $\gamma^{\prime\prime}$. These chains
satisfy three conditions: $\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]=b_{t^{\prime}}$, $\partial\gamma^{\prime\prime}\setminus
K[X_{t^{\prime\prime}}]=b_{t^{\prime\prime}}$, and
$(\partial\gamma^{\prime}+\partial\gamma^{\prime\prime})\cap K[X_{t}]=\beta$.
To find the minimal chain that spans $\beta$ at $t$, we only need to consider
minimal chains $\gamma^{\prime}$ and $\gamma^{\prime\prime}$ with properties.
The following formula for $\mathbf{V}[\beta,t]$ confirms this.

######  Lemma 5.14.

Let $\beta\in C_{d{-}1}(K[X_{t}])$. Then

$\mathbf{V}[\beta,t]=\underset{\beta^{\prime},\beta^{\prime\prime}}{\min}\;\mathbf{V}[\beta^{\prime},t^{\prime}]+\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$

where the minimization ranges over $\beta^{\prime}$ and $\beta^{\prime\prime}$
such that

  * •

$\beta^{\prime}\in C_{d{-}1}(K[X_{t^{\prime}}])$

  * •

$\beta^{\prime\prime}\in C_{d{-}1}(K[X_{t^{\prime\prime}}])$

  * •

$\beta^{\prime}+\beta^{\prime\prime}=\beta$

###### Proof.

We first show that each chain on the right hand side of the equation spans
$\beta$ at $t$. Let $\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$ and
$\gamma^{\prime\prime}\in C_{d}(K_{t^{\prime\prime}})$ such that
$\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$,
$\gamma^{\prime\prime}$ spans $\beta^{\prime\prime}$ at $t^{\prime\prime}$,
and $\beta^{\prime}+\beta^{\prime\prime}=\beta$. We claim that
$\gamma=\gamma^{\prime}+\gamma^{\prime\prime}$ spans $\beta$ at $t$. This
follows as

$\displaystyle\partial\gamma\cap K[X_{t}]=$
$\displaystyle(\partial\gamma^{\prime}\cap
K[X_{t}])+(\partial\gamma^{\prime\prime}\cap K[X_{t}])$ $\displaystyle=$
$\displaystyle\beta^{\prime}+\beta^{\prime\prime}$ $\displaystyle=$
$\displaystyle\beta.$

and

$\displaystyle\partial\gamma\setminus K[X_{t}]=$
$\displaystyle(\partial\gamma^{\prime}\setminus
K[X_{t}])+(\partial\gamma^{\prime\prime}\setminus K[X_{t}])$ $\displaystyle=$
$\displaystyle b_{t^{\prime}}+b_{t^{\prime\prime}}$ $\displaystyle=$
$\displaystyle b_{t}$ (by Corollary 5.13)

Moreover, $\|\gamma\|=\|\gamma^{\prime}\|+\|\gamma^{\prime\prime}\|$ as
$\gamma^{\prime}$ and $\gamma^{\prime\prime}$ are disjoint. If
$\gamma^{\prime}$ and $\gamma^{\prime\prime}$ achieve
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ and
$\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$, then
$\|\gamma\|=\mathbf{V}[\beta^{\prime},t]+\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$.

Now let $\gamma\in C_{d}(K_{t})$ be the minimum weight chain that spans
$\beta$ at $t$. By Lemma 5.12, $\gamma=\gamma^{\prime}+\gamma^{\prime\prime}$
for some $\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$ and
$\gamma^{\prime\prime}\in C_{d}(K_{t^{\prime\prime}})$. Let
$\beta^{\prime}=\partial\gamma^{\prime}\cap K[X_{t^{\prime}}]$ and
$\beta^{\prime\prime}=\partial\gamma^{\prime\prime}\cap
K[X_{t^{\prime\prime}}]$. We will show that $\gamma^{\prime}$ and
$\gamma^{\prime\prime}$ achieve $\mathbf{V}[\beta^{\prime},t^{\prime}]$ and
$\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$ respectively.

We first show that $\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$.
We already know that $\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]=\beta^{\prime}$, so we only need to prove that
$\partial\gamma^{\prime}\setminus K[X_{t^{\prime}}]=b_{t^{\prime}}$. We
consider the intersection $(\partial\gamma\setminus K[X_{t}])\cap
K_{t^{\prime}}$. We see that

$\displaystyle(\partial\gamma\setminus K[X_{t}])\cap K_{t^{\prime}}=$
$\displaystyle(\partial\gamma^{\prime}\setminus K[X_{t}])\cap
K_{t^{\prime}}+(\partial\gamma^{\prime\prime}\setminus K[X_{t}])\cap
K_{t^{\prime}}$ $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}\setminus K[X_{t}])\cap K_{t^{\prime}}$
(*) $\displaystyle=$ $\displaystyle\partial\gamma^{\prime}\setminus K[X_{t}]$
(as $\partial\gamma^{\prime}\subset K_{t^{\prime}}$.)

where line (*) follows from the fact that
$(\partial\gamma^{\prime\prime}\setminus K[X_{t}])\cap
K_{t^{\prime}}=\emptyset$. This is the case as
$\partial\gamma^{\prime\prime}\setminus K[X_{t}]\subset
K_{t^{\prime\prime}}\setminus K[X_{t}]$ and $K_{t}^{\prime}\setminus
K[X_{t^{\prime}}]$ and $K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]$
are disjoint by Lemma 5.11.

We can alternatively express $(\partial\gamma\setminus K[X_{t}])\cap
K_{t^{\prime}}$ as

$\displaystyle(\partial\gamma\setminus K[X_{t}])\cap K_{t^{\prime}}=$
$\displaystyle b_{t}\cap K_{t^{\prime}}$ $\displaystyle=$ $\displaystyle
b_{t^{\prime}}\cap K_{t^{\prime}}+b_{t^{\prime\prime}}\cap
K_{t^{\prime\prime}}$ (by Corollary 5.13) $\displaystyle=$ $\displaystyle
b_{t^{\prime}}\cap K_{t^{\prime}}$ (*) $\displaystyle=$ $\displaystyle
b_{t^{\prime}}$ (as $b_{t^{\prime}}\subset K_{t^{\prime}}$.)

where (*) follows as $b_{t^{\prime\prime}}\cap K_{t^{\prime}}=\emptyset$. This
is true as $b_{t^{\prime\prime}}\subset K_{t^{\prime\prime}}\setminus
K[X_{t}]$ and $K_{t}^{\prime}\setminus K[X_{t^{\prime}}]$ and
$K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]$ are disjoint by Lemma
5.11. Thus $\partial\gamma^{\prime}\setminus K[X_{t}]=(\partial\gamma\setminus
K[X_{t}])\cap K_{t^{\prime}}=b_{t^{\prime}}$ and $\gamma^{\prime}$ spans
$\beta^{\prime}$ at $t^{\prime}$. The proof that $\gamma^{\prime\prime}$ spans
$\beta^{\prime\prime}$ at $t^{\prime\prime}$ is symmetrical.

As $\gamma$ is the minimum weight chain that spans $\beta$ at $t$, then
$\gamma^{\prime}$ and $\gamma^{\prime\prime}$ must be the chains that achieve
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ and
$\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$ respectively. We saw in
the first paragraph that any two chains $\gamma^{\prime}$ and
$\gamma^{\prime\prime}$ that span $\beta^{\prime}$ at $t^{\prime}$ and
$\beta^{\prime\prime}$ at $t^{\prime\prime}$ sum to span $\beta$ at $t$. So if
(say) $\gamma^{\prime}$ did not achieve
$\mathbf{V}[\beta^{\prime},t^{\prime}]$, we could replace $\gamma^{\prime}$
with the chain $\gamma^{\prime}_{o}$ that achieves
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ and
$\gamma^{\prime}_{o}+\gamma^{\prime\prime}$ would be a chain with strictly
lower weight that spans $\beta$ at $t$, contradicting the assumed optimality
of $\gamma$. ∎

###  5.5 Analysis

We now analyze the running time of the dynamic program, thereby proving
Theorem 1.1.

###### Proof of Theorem 1.1.

We first show that we can compute the dynamic programming table entry for each
type of node in $T$ in $2^{O\left(k^{d}\right)}$ time.

We can compute the entry at the leaf node in constant time as we are entering
in a single table entry.

We can compute the value $V[\beta,t]$ of each $(d{-}1)$-chain $\beta$ at an
introduce node in constant time. As there are
$O(\binom{k+1}{d})=O\left((k+1)^{d}\right)$ $(d{-}1)$-simplices in $K[X_{t}]$,
then there are $2^{O\left(k^{d}\right)}$ $(d{-}1)$-chains in
$C_{d{-}1}(K[X_{t}])$. Processing an introduce node thus takes
$2^{O\left(k^{d}\right)}$ time in total.

We compute the entry at a forget node by performing nested iterations over
$C_{d{-}1}(K[X_{t}])$ and $C_{d}^{w}(K[X_{t}])$. There are
$O(\binom{k+1}{d})=O\left((k+1)^{d}\right)$ $(d{-}1)$-simplices in $K[X_{t}]$,
so there are $2^{O\left(k^{d}\right)}$ $(d{-}1)$-chains $\beta\in
C_{d{-}1}(K[X_{t}])$. There are likewise $O(\binom{k+1}{d})=O(k^{d})$
$d$-simplices (we choose $d$ vertices in addition to $w$) in
$(K[X_{t^{\prime}}])_{d}^{w}$ and $2^{O(k^{d})}$ chains $\gamma_{w}\in
C_{d}^{w}(K[X_{t^{\prime}}])$. The size of both of the chain groups
$C_{d{-}1}(K[X_{t^{\prime}}])$ and $C_{d}^{w}(K[X_{t^{\prime}}])$ is at most
$2^{O\left(k^{d}\right)}$, so the nested iteration over both of these groups
takes $2^{O\left(k^{d}\right)}$ time.

We compute the entry at a join node by iterating over the chain groups
$C_{d{-}1}(K[X_{t^{\prime}}])$ and $C_{d{-}1}(K[X_{t^{\prime\prime}}])$, which
takes $2^{O\left(k^{d}\right)}$ time.

There are $O(kn)$ nodes in a nice tree decomposition, and the dynamic
programming table entry at each node can be computed in
$2^{O\left(k^{d}\right)}$ time. The algorithm therefore takes
$2^{O\left(k^{d}\right)}n$ time in total. As $d\leq k$ by Corollary 3.4, the
running time of our algorithm is also $2^{O\left(k^{k}\right)}n$. ∎

As a corollary, we can test whether two $d{-}1$ chains $b$ and $h$ are
homologous by running our algorithm on $b+h$. The chains $b$ and $h$ are
homologous if and only if $\mathbf{V}[\emptyset,r]<\infty$. Hence, we obtain
Corollary 1.2. This implies we can use our algorithm to test whether or not a
($d{-}1$)-cycle $b$ is null-homologous, which is to say, whether $b$ is
homologous to the empty chain.

Our algorithm uses the Hamming norm to measure the weight of a chain, but our
algorithm can be easily adapted to solve OBCP in a simplicial complex with
weight $d$-simplices. If $w:K_{d}\to\mathbb{R}^{+}$ is a weight function on
the $d$-simplices, we define a weight function on $d$-chains
$w:C_{d}(K)\to\mathbb{R}^{+}$ such that
$w(\gamma)=\sum_{\sigma\in\gamma}w(\sigma)$ is the weight of the chain
$\gamma$. If we substitute $w(\gamma)$ for $\|\gamma\|$ everywhere in our
algorithm for OBCP, it is easy to see this adapted algorithm finds the minimum
weight chain $c$ bounded by $b$.

##  6 Optimal Homologous Chain Problem

Let $K$ be a simplicial complex and let $b\in C_{d{-}1}(K)$. The Optimal
Homologous Chain Problem asks to find the minimum weight $(d{-}1)$-chain $h\in
C_{d{-}1}(K)$ such that $b+h=\partial c$ for some $c\in C_{d}(K)$. Let $(T,X)$
be a nice tree decomposition of $K$. We will find $h$ using a dynamic program
on $T$.

Any chain $c\in C_{d}(K)$ defines a chain homologous to $b$, namely
$h=\partial c+b$. Instead of searching for the $(d{-}1)$-chain $h$, we can
therefore search for the $d$-chain $c$ that minimizes the weight $\|\partial
c+b\|$. The chain $c$ also defines the minimum chain homologous to $b$ in a
local sense. If we restrict this chain to a subcomplex $K_{t}$, we find that
$c\cap K_{t}$ is the chain that minimizes $\|\partial(c\cap K_{t})\setminus
K[X_{t}]+b_{t}\|$ over all chains with boundary satisfying $\partial(c\cap
K_{t})\cap K[X_{t}]=\beta$. Accordingly, for each $(d{-}1)$-chain $\beta\in
C_{d{-}1}(K[X_{t}])$, we store the dynamic programming table entry

$\mathbf{V}[\beta,t]=\underset{\underset{\partial\gamma\cap
K[X_{t}]=\beta}{\gamma\in C_{d}(K_{t}):}}{\min}\|\partial\gamma\setminus
K[X_{t}]+b_{t}\|.$

We say a $d$-chain $\gamma$ spans $\boldsymbol{\beta}$ at t if
$\partial\gamma\cap K[X_{t}]=\beta$. Lemma 6.1 shows that the table
$\mathbf{V}$ contains the weight of the optimal solution.

######  Lemma 6.1.

The entry $\mathbf{V}[\emptyset,r]$ is the minimum weight $\|\partial c+b\|$
for any chain $c\in C_{d}(K)$.

###### Proof.

The unique entry at the root $\mathbf{V}[\emptyset,r]$ contains the weight of
the minimum weight $(d{-}1)$-chain homologous to $b$. The bag at the root
$X_{t}$ is empty, so $K[X_{r}]=\emptyset$. Moreover, $V_{r}=V$, so $K_{r}=K$
and $b_{r}=b$. Thus, $\mathbf{V}[\emptyset,r]$ contains the minimum weight
$\|\partial c\setminus K[X_{r}]+b\|=\|\partial c+b\|$ for any chain $c\in
C_{d}(K_{r})=C_{d}(K)$. ∎

Our algorithm for OHCP is similar to our algorithm for OBCP as we are
searching for a $d$-chain $c$, except we are optimizing a different function.
We perform a dynamic program on our tree decomposition, and at each node $t$,
we store the weight of the chain $\gamma\in C_{d}(K_{t})$ that spans each
$(d{-}1)$-chain $\beta\in C_{d{-}1}(K[X_{t}])$ and minimizes the objective
function. We construct the chain $\gamma$ using the orthogonal decompositions
of the chain groups $C_{d}(K_{t})$ from Section 5. At each node, the two
algorithms will loop over the same chain groups. Accordingly, the running time
for our algorithm for OHCP is the same as the running time for our algorithm
for OBCP, and we obtain Theorem 1.3.

We now present our dynamic program for OHCP. We compute the entries of
$\mathbf{V}$ at a node $t$ using the entries of $\mathbf{V}$ at the children
of $t$. Accordingly, we only need to specify how to compute $t$ at each type
of node in a nice tree decomposition.

###  6.1 Leaf Nodes

Let $t$ be a leaf node. Recall that $X_{t}=\emptyset$, so
$K[X_{t}]=\emptyset$. Moreover, $t$ has no children, so
$V_{t}=K_{t}=b_{t}=\emptyset$. There is a unique $(d{-}1)$-chain
$\beta=\emptyset\in C_{d{-}1}(K[X_{t}])$ and a unique $d$-chain
$\gamma=\emptyset\in C_{d}(K_{t})$. The chain $\gamma$ spans $\beta$ at $t$,
so $\mathbf{V}[\emptyset,t]=0$.

###  6.2 Introduce Nodes

Let $t$ be an introduce node and $t^{\prime}$ the unique child of $t$. Recall
that $X_{t}=X_{t^{\prime}}\sqcup\\{w\\}$. Let $\beta\in C_{d{-}1}(K[X_{t}])$.
We claim the following formula for $\mathbf{V}[\beta,t]$.

######  Lemma 6.2.

Let $t$ be an introduce node and $t^{\prime}$ be its unique child. Let
$\beta\in C_{d-1}(K[X_{t}])$. Then

$\mathbf{V}[\beta,t]=\begin{cases}\mathbf{V}[\beta,t^{\prime}]&\text{ if
}\beta\in C_{d{-}1}(K[X_{t^{\prime}}])\\\ \infty&\text{ otherwise}\end{cases}$

###### Proof.

We will show that any chain that spans $\beta$ at $t^{\prime}$ spans $\beta$
at $t^{\prime}$ and vice versa. Let $\gamma\in C_{d}(K_{t^{\prime}})$ such
that $\gamma$ spans $\beta$ at $t^{\prime}$; that is, $\partial\gamma\cap
K[X_{t^{\prime}}]=\beta$. We need to show that $\partial\gamma\cap
K[X_{t}]=\beta=\partial\gamma\cap K[X_{t^{\prime}}]$ as well. We do this by
proving the equivalent statement that $\partial\gamma\setminus
K[X_{t}]=\partial\gamma\setminus K[X_{t^{\prime}}].$ As $\partial\gamma\in
K_{t}\cap K_{t^{\prime}}$, then

$\displaystyle\partial\gamma\setminus K[X_{t^{\prime}}]=$
$\displaystyle\partial\gamma\cap(K_{t^{\prime}}\setminus K[X_{t^{\prime}}])$
(as $\partial\gamma\subset K_{t^{\prime}}$) $\displaystyle=$
$\displaystyle\partial\gamma\cap(K_{t}\setminus K[X_{t}])$ (as $K_{t}\setminus
K[X_{t}]=K_{t^{\prime}}\setminus K[X_{t^{\prime}}]$ by Lemma 5.4)
$\displaystyle=$ $\displaystyle\partial\gamma\setminus K[X_{t}].$ (as
$\partial\gamma\subset K_{t}$)

As a corollary, we see that $\partial\gamma\cap K[X_{t}]=\partial\gamma\cap
K[X_{t^{\prime}}]=\beta$. So if $\gamma$ spans $\beta$ at $t$, then $\gamma$
spans $\beta$ at $t^{\prime}$ and vice versa. Moreover, as
$b_{t}=b_{t^{\prime}}$ by Lemma 5.6, then $\|\partial\gamma\cap
K[X_{t}]+b_{t}\|=\|\partial\gamma\cap K[X_{t^{\prime}}]+b_{t^{\prime}}\|$. So
$\mathbf{V}[\beta,t]=\mathbf{V}[\beta,t]$ for each $(d{-}1)$-chain $\beta$ in
$C_{d{-}1}(K_{t^{\prime}})$.

As $\partial\gamma\cap K[X_{t}]=\partial\gamma\cap K[X_{t^{\prime}}]$ for each
$\gamma\in C_{d}(K_{t})$, then if $\beta\in C_{d}(K[X_{t}])\setminus
C_{d}(K[X_{t^{\prime}}])$, no chain spans $\beta$ at $t$. Accordingly, we set
$\mathbf{V}[\beta,t]=\infty$. ∎

###  6.3 Forget Nodes

Let $t$ be a forget node and $t^{\prime}$ the unique child of $t$. Recall that
$X_{t}\sqcup\\{w\\}=X_{t^{\prime}}$. Let $\gamma\in C_{d}(K_{t})$. We can
decompose $\gamma=\gamma^{\prime}+\gamma_{w}$ where $\gamma^{\prime}\in
C_{d}(K_{t^{\prime}})$ and $\gamma_{w}\in C_{d}^{w}(K[X_{t}])$. Let
$\beta^{\prime}=\partial\gamma^{\prime}\cap K[X_{t^{\prime}}]$.

We want to find $\gamma$ that minimizes the weight of the chain
$\partial\gamma\setminus K[X_{t}]+b_{t}$. We can decompose the chain
$\partial\gamma\setminus K[X_{t}]+b_{t}$ into $(\partial\gamma\setminus
K[X_{t}]+b_{t})\cap K[X_{t^{\prime}}]$ and $(\partial\gamma\setminus
K[X_{t}]+b_{t})\setminus K[X_{t^{\prime}}]$. We find that
$(\partial\gamma\setminus K[X_{t}]+b_{t})\cap
K[X_{t}]=(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]+b_{t}\cap
K[X_{t^{\prime}}]$ and $(\partial\gamma\setminus K[X_{t}]+b_{t})\setminus
K[X_{t^{\prime}}]=\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}}$. Decomposing $\partial\gamma\setminus
K[X_{t}]+b_{t}$ this way gives us a quick way to calculate
$\|\partial\gamma\setminus K[X_{t}]+b_{t}\|$. The chain
$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]+b_{t}\cap
K[X_{t^{\prime}}]$ is contained entirely in $C_{d-1}(K[X_{t^{\prime}}])$, so
its weight can be calculated in $O(k^{d})$ time. Likewise, if
$\gamma^{\prime}$ is the chain that minimizes
$\partial\gamma^{\prime}\setminus K[X_{t^{\prime}}]+b_{t^{\prime}}$ (which we
will prove is the case for $\gamma$ that minimizes $\|\partial\gamma\setminus
K[X_{t}]+b_{t}\|$,) then the weight of
$(\partial\gamma^{\prime}+b_{t^{\prime}})\setminus K[X_{t^{\prime}}]$ has
already been computed and is stored in
$\mathbf{V}[\beta^{\prime},t^{\prime}]$. This justifies the following formula
for $\mathbf{V}[\beta,t]$.

######  Lemma 6.3.

Let $t$ be a forget node and $t^{\prime}$ the unique child of $t$. Let
$\beta\in C_{d-1}(K[X_{t}])$. Then

$V[\beta,t]=\underset{\beta^{\prime},\gamma_{w}}{\min}\;\mathbf{V}[\beta^{\prime},t^{\prime}]+\|(\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]+b_{t}\cap K[X_{t^{\prime}}]\|$

where the minimization ranges over $\beta^{\prime}$ and $\gamma_{w}$ such that

  * •

$\beta^{\prime}\in C_{d{-}1}(K[X_{t^{\prime}}]$

  * •

$\gamma_{w}\in C_{d}^{w}(K[X_{t^{\prime}}])$

  * •

$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$

###### Proof.

We first show that any chain on the right hand side of the equation in the
lemma spans $\beta$ at $t$. Let $\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$
that achieves $\mathbf{V}[\beta^{\prime},t]$ and let $\gamma_{w}\in
C_{d}^{w}(K[X_{t^{\prime}}])$ such that
$(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$. Let
$\gamma=\gamma^{\prime}+\gamma_{w}$. Observe that $\partial\gamma\cap
K[X_{t}]\cap K[X_{t^{\prime}}]=\partial\gamma\cap K[X_{t}]$ as
$K[X_{t}]\subset K[X_{t^{\prime}}]$. We find that

$\displaystyle\partial\gamma\cap K[X_{t}]=$ $\displaystyle\partial\gamma\cap
K[X_{t^{\prime}}]\cap K[X_{t}]$ $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]+\partial\gamma_{w}\cap K[X_{t^{\prime}}])\cap K[X_{t}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}$) $\displaystyle=$
$\displaystyle(\beta^{\prime}+\partial\gamma_{w}\cap K[X_{t^{\prime}}])\cap
K[X_{t}]$ (as $\gamma^{\prime}$ spans $\beta^{\prime}$ at $t^{\prime}$)
$\displaystyle=$ $\displaystyle(\beta^{\prime}+\partial\gamma_{w})\cap
K[X_{t}]$ (as $\gamma^{\prime}\subset K[X_{t^{\prime}}]$) $\displaystyle=$
$\displaystyle\beta$ (by assumption)

This proves that $\gamma$ indeed spans $\beta$ at $t$. This proof also works
in the opposite direction. If $\gamma$ spans $\beta$ at $t$, and $\gamma$
decomposes $\gamma=\gamma^{\prime}+\gamma_{w}$ for $\gamma^{\prime}\in
C_{d}(K_{t^{\prime}})$, $\gamma_{w}\in C_{d}^{w}(K[X_{t^{\prime}}])$, and
$\partial\gamma^{\prime}\cap K[X_{t^{\prime}}]=\beta^{\prime}$, then this
prove that $(\beta^{\prime}+\partial\gamma_{w})\cap K[X_{t}]=\beta$.

Next, we show that our algorithm calculates the weight of $\gamma$ correctly;
that is, $\|\partial\gamma\setminus
K[X_{t}]+b_{t}\|=\mathbf{V}[\beta^{\prime},t^{\prime}]+\|(\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]+b_{t}\cap K[X_{t^{\prime}}]\|$. As the table entry is defined
$\mathbf{V}[\beta^{\prime},t^{\prime}]=\|\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t}\|$, we can show the formula is correct by showing that
$\partial\gamma\setminus K[X_{t}]+b_{t}$ decomposes into

$\partial\gamma\setminus K[X_{t}]+b_{t}=(\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t})\sqcup((\beta^{\prime}+\partial\gamma_{w})\setminus
K[X_{t}]+b_{t}\cap K[X_{t^{\prime}}]).$

As a first step, we decompose $\partial\gamma\setminus K[X_{t}]+b_{t}$ into
the two disjoint sets $(\partial\gamma\setminus K[X_{t}]+b_{t})\cap
K[X_{t^{\prime}}]$ and $(\partial\gamma\setminus K[X_{t}]+b_{t})\setminus
K[X_{t^{\prime}}]$. In fact, these two sets will equal
$(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]+b_{t}\cap
K[X_{t^{\prime}}]$ and $\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}}$ respectively. If we intersect
$\partial\gamma\setminus K[X_{t}]+b_{t}$ with $K[X_{t^{\prime}}]$, we find
that

$\displaystyle(\partial\gamma\setminus K[X_{t}]+b_{t})\cap K[X_{t^{\prime}}]=$
$\displaystyle((\partial\gamma\setminus K[X_{t}])\cap
K[X_{t^{\prime}}])+(b_{t}\cap K[X_{t^{\prime}}])$ $\displaystyle=$
$\displaystyle((\partial\gamma\cap K[X_{t^{\prime}}])\setminus
K[X_{t}])+(b_{t}\cap K[X_{t^{\prime}}])$ (reordering) $\displaystyle=$
$\displaystyle(\beta^{\prime}+\partial\gamma_{w})\setminus K[X_{t}]+b_{t}\cap
K[X_{t^{\prime}}]$ (*)

where line (*) uses the fact $\partial\gamma\cap
K[X_{t^{\prime}}]=\beta^{\prime}+\partial\gamma_{w}$ that was proved in the
first paragraph of this proof. If we subtract $K[X_{t^{\prime}}]$ from
$\partial\gamma\setminus K[X_{t^{\prime}}]+b_{t}$, we find

$\displaystyle(\partial\gamma\setminus K[X_{t}]+b_{t})\setminus
K[X_{t^{\prime}}]=$ $\displaystyle\partial\gamma\setminus K[X_{t}]\setminus
K[X_{t^{\prime}}]+b_{t}\setminus K[X_{t^{\prime}}]$ $\displaystyle=$
$\displaystyle\partial\gamma\setminus K[X_{t^{\prime}}]+b_{t}\setminus
K[X_{t^{\prime}}]$ (as $K[X_{t}]\subset K[X_{t^{\prime}}]$) $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma_{w})\setminus
K[X_{t^{\prime}}]+b_{t}\setminus K[X_{t^{\prime}}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma_{w}$) $\displaystyle=$
$\displaystyle\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t}\setminus K[X_{t^{\prime}}]$ (as
$\partial\gamma_{w}\subset K[X_{t^{\prime}}]$) $\displaystyle=$
$\displaystyle\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}}$ (as $b_{t}\setminus
K[X_{t^{\prime}}]=b_{t^{\prime}}$ by Lemma 5.9)

Finally, we prove that the chain $\gamma$ that attains $\mathbf{V}[\beta,t]$
is included on the right hand side of the equation. We saw in the first
paragraph that we can write $\gamma$ as $\gamma=\gamma^{\prime}+\gamma_{w}$
where $\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$ and $\gamma_{w}\in
C_{d}^{w}(K[X_{t}])$. If $\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]=\beta^{\prime}$, it is easy to see that $\gamma^{\prime}$
must achieve $\mathbf{V}[\beta^{\prime},t^{\prime}]$; otherwise, we could
substitute $\gamma^{\prime}$ for the chain that achieves
$\mathbf{V}[\beta^{\prime},t^{\prime}]$ and get a strictly smaller chain. ∎

###  6.4 Join Nodes

Let $t$ be a join node, and let $t^{\prime}$ and $t^{\prime\prime}$ be the two
children of $t$. Recall that $X_{t}=X_{t^{\prime}}=X_{t^{\prime\prime}}$. Let
$\beta\in C_{d{-}1}(K[X_{t}])$. We claim the following formula for
$\mathbf{V}[\beta,t]$.

######  Lemma 6.4.

Let $t$ be a join node, and let $t^{\prime}$ and $t^{\prime\prime}$ be its two
children. Let $\beta\in C_{d{-}1}(K[X_{t}])$. Then

$\mathbf{V}[\beta,t]=\underset{\beta^{\prime},\beta^{\prime\prime}}{\min}\mathbf{V}[\beta^{\prime},t^{\prime}]+\mathbf{V}[\beta^{\prime\prime},t^{\prime\prime}]$

where the minimization ranges over $\beta^{\prime}$ and $\beta^{\prime\prime}$
such that

  * •

$\beta^{\prime}\in C_{d{-}1}(K[X_{t^{\prime}}])$

  * •

$\beta^{\prime\prime}\in C_{d{-}1}(K[X_{t^{\prime\prime}}])$

  * •

$\beta^{\prime}+\beta^{\prime\prime}=\beta$

###### Proof.

Let $\beta\in C_{d{-}1}(K_{t})$, and let $\gamma$ span $\beta$ at $t$. By
Lemma 5.12, $\gamma=\gamma^{\prime}+\gamma^{\prime\prime}$ where
$\gamma^{\prime}\in C_{d}(K_{t^{\prime}})$ and $\gamma^{\prime\prime}\in
C_{d}(K_{t^{\prime\prime}})$. Let $\beta^{\prime}=\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]$ and $\beta^{\prime\prime}=\partial\gamma^{\prime\prime}\cap
K[X_{t^{\prime\prime}}]$. Clearly,

$\displaystyle\beta=$ $\displaystyle\partial\gamma\cap K[X_{t}]$
$\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma^{\prime\prime})\cap
K[X_{t}]$ $\displaystyle=$ $\displaystyle\partial\gamma^{\prime}\cap
K[X_{t}]+\partial\gamma^{\prime\prime}\cap K[X_{t}]$ $\displaystyle=$
$\displaystyle\partial\gamma^{\prime}\cap
K[X_{t^{\prime}}]+\partial\gamma^{\prime\prime}\cap K[X_{t^{\prime\prime}}]$
(as $K[X_{t}]=K[X_{t^{\prime}}]=K[X_{t^{\prime\prime}}]$) $\displaystyle=$
$\displaystyle\beta^{\prime}+\beta^{\prime\prime}.$

This proof works in the reverse direction as well. If $\gamma^{\prime}$ spans
$\beta^{\prime}$ and $t^{\prime}$, $\gamma^{\prime\prime}$ spans
$\beta^{\prime\prime}$ at $t^{\prime\prime}$, and
$\beta^{\prime}+\beta^{\prime\prime}=\beta$, then
$\gamma^{\prime}+\gamma^{\prime\prime}$ spans $\beta$ at $t$.

Next, we prove that the formula correctly calculates the weight of $\gamma$.
We first prove that $\partial\gamma\setminus
K[X_{t}]+b_{t}=(\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}})\sqcup(\partial\gamma^{\prime\prime}\setminus
K[X_{t^{\prime\prime}}]+b_{t^{\prime\prime}})$. We consider the intersection

$\displaystyle\partial\gamma\setminus K[X_{t}]=$
$\displaystyle\partial\gamma\cap K_{t}\setminus K[X_{t}]$ $\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma^{\prime\prime})\cap
K_{t}\setminus K[X_{t}]$ (as
$\partial\gamma=\partial\gamma^{\prime}+\partial\gamma^{\prime\prime}$)
$\displaystyle=$
$\displaystyle(\partial\gamma^{\prime}+\partial\gamma^{\prime\prime})\cap(K_{t^{\prime}}\setminus
K[X_{t^{\prime}}]+K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}])$ (by
Lemma 5.11)

As $\partial\gamma^{\prime}\subset K_{t^{\prime}}$,
$\partial\gamma^{\prime\prime}\subset K_{t^{\prime\prime}}$, and
$K_{t^{\prime}}\setminus K[X_{t^{\prime}}]$ and $K_{t^{\prime\prime}}\setminus
K[X_{t^{\prime\prime}}]$ are disjoint, we distribute and see that

$\partial\gamma\setminus K[X_{t}]=\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+\partial\gamma^{\prime\prime}\setminus
K[X_{t^{\prime\prime}}]$

Now if we consider the intersection

$\displaystyle\partial\gamma\setminus K[X_{t}]+b_{t}=$
$\displaystyle(\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+\partial\gamma^{\prime\prime}\setminus
K[X_{t^{\prime\prime}}])+(b_{t^{\prime}}+b_{t^{\prime\prime}})$ (by Corollary
5.13 ) $\displaystyle=$ $\displaystyle(\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}})\sqcup(\partial\gamma^{\prime}\setminus
K[X_{t^{\prime\prime}}]+b_{t^{\prime\prime}})$

where the second line follows as $\partial\gamma\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}}\subset K_{t^{\prime}}\setminus
K[X_{t^{\prime}}]$, $\partial\gamma\setminus
K[X_{t^{\prime\prime}}]+b_{t^{\prime\prime}}\subset
K_{t^{\prime\prime}}\setminus K[X_{t^{\prime\prime}}]$, and
$K_{t^{\prime}}\setminus K[X_{t^{\prime}}]$ and $K_{t^{\prime\prime}}\setminus
K[X_{t^{\prime\prime}}]$ are disjoint. Thus, $\|\partial\gamma\setminus
K[X_{t}]+b_{t}\|=\|\partial\gamma^{\prime}\setminus
K[X_{t^{\prime}}]+b_{t^{\prime}}\|+\|\partial\gamma^{\prime\prime}\setminus
K[X_{t^{\prime\prime}}]+b_{t^{\prime\prime}}\|$.

As the sum of any two chains $\gamma^{\prime}$ and $\gamma^{\prime\prime}$
that span $\beta^{\prime}$ at $t^{\prime}$ and $\beta^{\prime\prime}$ at
$t^{\prime\prime}$ spans $\beta$ at $t$, it is easy to see that the optimal
chain that span $\beta$ at $t$ must be composed of optimal chains that span
$\beta^{\prime}$ at $t^{\prime}$ and $\beta^{\prime\prime}$ at
$t^{\prime\prime}$ respectively. ∎

##  7 Comparison with Other Algorithms

In this section, we compare our algorithms for OHCP and OBCP to the algorithms
introduced by Blaser and Vȧgset [5] and Blaser et al. [4]. Our algorithm and
their algorithms are parameterized by the treewidth of different graphs
associated with a simplicial complex, so we compare the treewidth of the
1-skeleton to the treewidth of these graphs. We start by defining these
graphs.

The d-connectivity graph is the graph $Con_{d}(K)$ with the $d$-simplices
$K_{d}$ as vertices and pairs of $d$-simplices that share a $(d{-}1)$-face as
edges. Level d of the Hasse diagram is the graph $Hasse_{d}(K)$ with the
$(d{-}1)$ and $d$-simplices $K_{d-1}\cup K_{d}$ as vertices and edges between
$d$-simplices and their $(d{-}1)$-faces.

Our algorithms for OHCP and OBCP run in $2^{O(k^{d})}n$ time, where $k$ is the
treewidth of the 1-skeleton and $n$ is the number of vertices in the complex.
Blaser and Vȧgset introduce two algorithms for OHCP: one algorithm uses the
$d$-connectivity graph, and the other algorithm uses level $d$ of the Hasse
diagram of $K$. The algorithms of Blaser and Vȧgset run in $O(2^{l(2d+5)}m)$
and $O(2^{2l}m)$ time respectively, where $l$ is the treewidth and $m$ is the
number of vertices in the given graph. Blaser et al. introduce an algorithm
for OBCP that runs in $O(4^{l}m)$ time where $l$ is the treewidth and $m$ is
the number of vertices of the Hasse diagram. Note that for the
$d$-connectivity graph and level $d$ of the Hasse diagram, the number of
vertices $m$ are $O(\binom{n}{d+1})$ and $O(\binom{n}{d}+\binom{n}{d+1})$
respectively, and these bounds can be tight.

The goal of this section is to compare the treewidth of the graphs used by our
algorithm and by the algorithms of Blaser and Vȧgset and Blaser et al. The
following theorem by Blaser and Vȧgset compare the treewidth of $Con_{d}(K)$
and $Hasse_{d}(K)$

######  Theorem 7.1 (Proposition 7.1, Blaser and Vȧgset [5]).

Let $K$ be a simplicial complex. The treewidth
$\operatorname{tw}(Hasse_{d}(K))\leq\operatorname{tw}(Con_{d}(K))+1$; however,
$\operatorname{tw}(Con_{d}(K))$ is not bounded by
$\operatorname{tw}(Hasse_{d}(K))$.

As the treewidth of $Hasse_{d}(K)$ is $O(\operatorname{tw}(Con_{d}(K)))$, we
will spend the rest of this section comparing the treewidth of $Hasse_{d}(K)$
and the treewidth of the 1-skeleton $K^{1}$. We will show that
$\operatorname{tw}(Hasse_{d}(K))\in O(\binom{\operatorname{tw}(K^{1})+1}{d})$.
We will then show that for a certain class of complexes, this upper bound is
nearly tight, i.e.
$\operatorname{tw}(Hasse_{d}(K))\in\Omega(\binom{\operatorname{tw}(K^{1})+1}{d}\cdot\frac{1}{d+1})$.
The first result implies that algorithms parameterized by
$\operatorname{tw}(Hasse_{d}(K))$ having running time
$O(2^{\operatorname{tw}(K^{1})^{d}}m)$; in other words, these algorithm have
(at worst) the same dependence on $\operatorname{tw}(K^{1})$ as our
algorithms. The second result implies that in some cases, the dependence on
$\operatorname{tw}(K^{1})$ is almost the same.

###  7.1 Upper Bounds

In this section, we provide an upper bound on the treewidth of level $d$ of
the Hasse diagram in terms of the treewidth of the 1-skeleton. The proof of
this theorem was developed with Nello Blaser and Erlend Raa Vȧgset.

######  Theorem 7.2.

Let $K$ be a simplicial complex. Then $\operatorname{tw}(Hasse_{d}(K))\in
O(\binom{\operatorname{tw}(K^{1})+1}{d})$.

###### Proof.

Let $(T,X)$ be any tree decomposition of $K^{1}$ of width $k$. We will use
$(T,X)$ as a starting point for constructing a tree decomposition of
$Hasse_{d}(K)$ of width $O(\binom{k+1}{d})$. For a node $t\in T$, we add all
$(d-1)$-simplices in $K[X_{t}]$ to a new bag $Y_{t}$. The size of any bag
$Y_{t}$ is $O(\binom{k+1}{d})$, as any set of $d$ vertices in $X_{t}$ may be a
$(d-1)$-simplex in $K$. By Corollary 3.3, each $(d-1)$-simplex $\sigma\in
Y_{t}$ for some $t\in T$ as $\sigma\subset X_{t}$ for some $t\in T$, and
moreover, the set of nodes $\\{t\in T:\sigma\in T\\}$ are connected.

Next, for each $d$-simplex $\tau\in K$, there is a node $t\in T$ such that
$\tau\subset X_{t}$ by Corollary 3.3. By construction, we conclude that each
$(d-1)$-face $\sigma$ of $\tau$ must be contained in the new bag $Y_{t}$. We
add a new node $t_{\tau}$ to the tree with bag
$Y_{t_{\tau}}=Y_{t}\cup\\{\tau\\}$, and we connect $t_{\tau}$ to $t$. The size
of $Y_{t_{\tau}}$ is $O(\binom{k+1}{d})$, as $Y_{t_{\tau}}$ contains one more
vertex than $Y_{t}$.

We now verify that this new tree decomposition satisfies the conditions to be
a tree decomposition. Each $(d-1)$-simplex $\sigma$ is contained in the bags
of the nodes $\\{t\in T:\sigma\subset
X_{t}\\}\cup\\{t_{\tau}:\sigma\subset\tau\\}$; the nodes $\\{t\in
T:\sigma\subset X_{t}\\}$ form a connected subtree as $(T,X)$ is a tree
decomposition, and each node $t_{\tau}$ is connected to some node in $\\{t\in
T:\sigma\subset X_{t}\\}$. Each $d$-simplex $\tau$ is contained in the single
bag $Y_{t_{\tau}}$. Finally, each edge in $Hasse_{d}(K)$ is a pair
$\\{\sigma,\tau\\}$ of a $(d-1)$-simplex $\sigma$ and a $d$-simplex $\tau$
such that $\sigma\subset\tau$. By construction, $\\{\sigma,\tau\\}\subset
Y_{t_{\tau}}$.

This proves there is a tree decomposition of $Hasse_{d}(K)$ of width
$O(\binom{k+1}{d})$ when $k$ is the width of any tree decomposition of
$K^{1}$. In particular, this proves that there is a tree decomposition of
width $O(\binom{\operatorname{tw}(K^{1})+1}{d})$. ∎

###  7.2 Lower Bounds

Let $\Delta^{n}$ be the simplicial complex that is the set of all subsets of a
set of vertices $V=\\{v_{1},\ldots,v_{n}\\}$. (Intuitively, $\Delta^{n}$ is a
$(n-1)$-simplex and all its faces.) Our main theorem of this section is a
lower bound of $\Omega(\binom{n}{d}\cdot\frac{1}{d+1})$ on
$\operatorname{tw}(Hasse_{d}(\Delta^{n}))$. The treewidth of the 1-skeleton
$\operatorname{tw}((\Delta^{n})^{1})=n-1$ as $(\Delta^{n})^{1}$ is a complete
graph, so this lower bound shows that the $\Delta^{n}$ is close to being a
worst-case for the treewidth of the Hasse diagram. Specifically, the lower
bound on $\operatorname{tw}(Hasse_{d}(\Delta^{n}))$ differs from the upper
bound on $\operatorname{tw}(Hasse_{d}(\Delta^{n}))$ of Theorem 7.2 by a
multiplicative factor of $d+1$.

####  7.2.1 Background: Vertex and Edge Expansion

We will obtain our lower bounds of $\operatorname{tw}(Hasse_{d}(\Delta^{n}))$
using the related notions of vertex and edge expansion. Let $G$ be a graph.
The vertex expansion of $G$ is

$VE(G)=\underset{S\subset
V(G):1\leq|S|\leq\frac{1}{2}|V(G)|}{\min}\frac{|N(S)|}{|S|}$

where $N(S)$ is the set of vertices in $V(G)\setminus S$ with a neighbor in
$S$. The vertex expansion of $G$ is closely tied to the treewidth of $G$, as
evidenced by the following lemma from Chandran and Subramian [15].

######  Lemma 7.3 (Chandran and Subramian, Lemma 9[15]).

Let $1\leq s\leq|V(G)|$. Define $N_{\min}(G,s)$ to be

$N_{\min}(G,s)=\underset{S\subset V(G):s/2\leq|S|\leq s}{\min}|N(S)|.$

Then $\operatorname{tw}(G)\geq N_{\min}(G,s)-1$.

######  Corollary 7.4.

Let $G$ be a graph. Then $\operatorname{tw}(G)\geq\frac{VE(G)\cdot|V(G)|}{4}$.

###### Proof of Corollary.

We obtain the corollary by setting $s=|V(G)|/2$. Using the definition of
vertex expansion, any set of vertices $S$ with at least $s/2=|V(G)|/4$
vertices satisfies $|N(S)|\geq VE(G)\cdot|S|\geq\frac{VE(G)\cdot|V(G)|}{4}$. ∎

We are able to get a lower bound on the vertex expansion (and by Corollary
7.4, a lower bound on the treewidth of $G$) using the related notion of edge
expansion. The edge expansion of a graph $G$ is

$EE(G)=\underset{S\subset
V(G):1\leq|S|\leq|V(G)|/2}{\min}\frac{|\delta(S)|}{|S|}$

where $\delta(S)$ is the set of edges with one endpoint in $S$ and one
endpoint in $V(G)\setminus S$. The following lemma relates the notion of edge
and vertex expansion.

######  Lemma 7.5.

Let $d_{\max}$ be the maximum degree of a vertex in $G$. Then
$VE(G)\geq\frac{EE(G)}{d_{\max}}$.

###### Proof.

Let $S\subset V(G)$ be a set of vertices such that $1\leq|S|\leq|V(G)|/2$.
Then $|N(S)|\geq|\delta(S)|/d_{\max}$ as each vertex in $N(S)$ is incident to
at most $d_{\max}$ edges in $\delta(S)$. If $S^{*}=\underset{S\subset
V(G):1\leq|S|\leq|V(G)|/2}{\arg\min}\frac{|N(S)|}{|S|}$, then

$VE(G)=\frac{|N(S^{*})|}{|S^{*}|}\geq\frac{|\delta(S^{*})|}{d_{\max}\cdot|S^{*}|}\geq\frac{EE(G)}{d_{\max}}$

∎

We can now combine Corollary 7.4 and Lemma 7.5 to get a lower bound on the
treewidth in terms of edge expansion.

######  Lemma 7.6.

Let $G$ be a graph. Then
$\operatorname{tw}(G)\geq\frac{EE(G)\cdot|V(G)|}{4\cdot d_{\max}}$.

####  7.2.2 Background: Edge Transitivity

We are able to get a lower bound on the edge expansion of
$Hasse_{d}(\Delta^{n})$ as $Hasse_{d}(\Delta^{n})$ is edge-transitive. Let $G$
be a graph. A graph automorphism is a bijection $\phi:V(G)\to V(G)$ such that
$\\{u,v\\}\in E(G)$ if and only if $\\{\phi(u),\phi(v)\\}\in E(G)$. A graph
$G$ is edge-transitive if for any two edges $\\{u_{1},v_{1}\\}$ and
$\\{u_{2},v_{2}\\}$ of $G$, there is an automorphism $\phi:V(G)\to V(G)$ such
that $\\{\phi(u_{1}),\phi(v_{1})\\}=\\{u_{2},v_{2}\\}$.

######  Lemma 7.7.

The graph $Hasse_{d}(\Delta^{n})$ is edge-transitive.

###### Proof.

Recall that $\Delta^{n}$ is the set of all subsets of a set
$V=\\{v_{1},\ldots,v_{n}\\}$, and $Hasse_{d}(\Delta^{n})$ has vertices that
are the set of all subsets of size $d$ and $d+1$ of $V$. As a stepping stone
to the lemma, we claim that any bijection of $f:V\to V$ defines a graph
automorphism $\phi_{f}:V(Hasse_{d}(\Delta^{n}))\to V(Hasse_{d}(\Delta^{n}))$.
Specifically, if $\sigma=\\{u_{1},\ldots,u_{d}\\}\in V(Hasse_{d}(\Delta^{n}))$
is a $(d-1)$-simplex, we define $\phi_{f}$ to map
$\phi_{f}(\sigma)=\\{f(u_{1}),\ldots,f(u_{d})\\}$. Note that
$\phi_{f}(\sigma)$ is a set with $d$ distinct elements as $f$ is a bijection;
or in other words, $\phi_{f}(\sigma)$ is a $(d-1)$-simplex. We define
$\phi_{f}$ analogously on $d$-simplices in $V(Hasse_{d}(\Delta^{n}))$.

We now must verify that $\phi_{f}$ is a graph automorphism. Any edge
$\\{\sigma,\tau\\}$ of $Hasse_{d}(\Delta^{n})$ is a pair of a $(d-1)$-simplex
$\sigma$ and a $d$-simplex $\tau$ such that $\sigma\subset\tau$. It is
straightforward to verify that if $\\{\sigma,\tau\\}$ is an edge of
$Hasse_{d}(\Delta^{n})$, then $\\{\phi_{f}(\sigma),\phi_{f}(\tau)\\}$ is also
an edge; indeed, $\phi_{f}(\sigma)$ and $\phi_{f}(\tau)$ are a $(d-1)$ and
$d$-simplex respectively, and $\phi_{f}(\sigma)\subset\phi_{f}(\tau)$ by
definition. It is also straightforward to verify the converse.

We now use this fact to show that $Hasse_{d}(\Delta^{n})$ is edge-transitive.
Let $\\{\sigma_{1},\tau_{1}\\}$ and $\\{\sigma_{2},\tau_{2}\\}$ be any two
edges of $Hasse_{d}(\Delta^{n})$ such that
$\sigma_{1}=\\{u_{0},\ldots,u_{d-1}\\}$, $\tau_{1}=\\{u_{0},\ldots,u_{d}\\}$,
$\sigma_{2}=\\{v_{0},\ldots,v_{d-1}\\}$, and
$\tau_{2}=\\{v_{0},\ldots,v_{d}\\}$. Let $f:V\to V$ be any bijection such that
$f(u_{i})=v_{i}$ for $0\leq i\leq d$. From the previous argument, the map $f$
defines a graph automorphism $\phi_{f}$ on $Hasse_{d}(\Delta^{n})$. It follows
immediately from the definition of $\phi_{f}$ that
$\phi_{f}(\sigma_{1})=\sigma_{2}$ and $\phi_{f}(\tau_{1})=\tau_{2}$. ∎

The following lemma by Babai and Szegedy [2] provides a lower bound on the
edge expansion of edge-transitive graphs. Let $a$ and $b$ be non-zero real
numbers. The harmonic mean of $a$ and $b$ is
$2\cdot\left(\frac{1}{a}+\frac{1}{b}\right)^{-1}$.

######  Lemma 7.8 (Babai and Szegedy, 1992).

Let $G$ be a simple, edge-transitive graph. Let $D$ be the diameter of $G$,
and let $r$ be the harmonic mean of the minimum and maximum degree of $G$. The
edge expansion of $G$ is $EE(G)\geq\frac{r}{2D}$.

####  7.2.3 Putting Everything Together

We now calculate the diameter $D$ of $Hasse_{d}(\Delta^{n})$ and the parameter
$r$ from the statement of Lemma 7.8.

######  Lemma 7.9.

The diameter $D$ of $Hasse_{d}(\Delta^{n})$ is bounded above by $2d+2$.

###### Proof.

Let $\sigma$ and $\tau$ be distinct vertices of $Hasse_{d}(\Delta^{n})$. We
claim there is a $|\sigma\oplus\tau|$-length path between $\sigma$ and $\tau$
in $Hasse_{d}(\Delta^{n})$, where $\sigma\oplus\tau$ is the symmetric
difference of the sets $\sigma$ and $\tau$. To prove this, we will show there
is a simplex $\sigma^{\prime}$ adjacent to $\sigma$ such that
$|\sigma^{\prime}\oplus\tau|=|\sigma\oplus\tau|-1$. This will imply the lemma,
as the largest symmetric difference between two simplices in
$Hasse_{d}(\Delta^{n})$ is between two disjoint $(d+1)$-simplices, where the
symmetric difference is $2d+2$.

We can prove the existence of $\sigma^{\prime}$ by induction. First consider
the case that $|\sigma\oplus\tau|=1$. Then we claim it must be the case that
$\sigma\subset\tau$ or $\tau\subset\sigma$. Indeed, if $\sigma\not\subset\tau$
and $\tau\not\subset\sigma$, then $|\sigma\oplus\tau|\geq 2$. In this case,
$\sigma^{\prime}=\tau$.

In the case that $|\sigma\oplus\tau|>1$, there are two possibilities. If
$\sigma$ is a $d$-simplex, then $\sigma^{\prime}=\sigma\setminus\\{v\\}$ for
any $v\in\sigma\setminus\tau$. If $\sigma$ is a $(d-1)$-simplex, then
$\sigma^{\prime}=\sigma\cup\\{v\\}$ for any $v\in\tau\setminus\sigma$. In both
cases, the simplex $\sigma^{\prime}$ is a vertex in $Hasse_{d}(\Delta^{n})$ by
the definition of $Hasse_{d}(\Delta^{n})$, and
$|\sigma^{\prime}\oplus\tau|=|\sigma\oplus\tau|-1$. ∎

######  Lemma 7.10.

Let $n\geq 2d+1$. The harmonic mean $r$ of the min and max degree of
$Hasse_{d}(\Delta^{n})$ of the $n$-simplex is bounded below by $d+1$.

###### Proof.

The degree of a vertex $\sigma\in V(Hasse_{d}(\Delta^{n}))$ is either $d+1$
and $n-d$ if $\sigma$ is a $d$ or $(d-1)$-simplex respectively, so $d+1$ and
$n-d$ are the maximum and minimum degree of $Hasse_{d}(\Delta^{n})$. We lower
bound the harmonic mean as

$\displaystyle 2\left(\frac{1}{d+1}+\frac{1}{n-d}\right)^{-1}$
$\displaystyle\geq 2\left(\frac{1}{d+1}+\frac{1}{d+1}\right)^{-1}$ (as $n\geq
2d+1$) $\displaystyle=d+1$

∎

We now have everything we need to lower bound the edge expansion of
$Hasse_{d}(\Delta^{n})$.

######  Lemma 7.11.

Let $n\geq 2d+1$. The edge expansion of $Hasse_{d}(\Delta^{n})$ is bounded
below by $\frac{1}{4}$.

###### Proof.

We can lower bound the edge expansion of $Hasse_{d}(\Delta^{n})$ by plugging
the values calculated in Lemma 7.9 and Lemma 7.10 into the formula given by
Lemma 7.8, namely
$EE(Hasse_{d}(\Delta^{n}))\geq\frac{r}{2D}=\frac{d+1}{2\cdot(2d+2)}=\frac{1}{4}.$
∎

######  Theorem 7.12.

Let $n\geq 2d+1$. The treewidth of $Hasse_{d}(\Delta^{n})$ is
$\Omega(\binom{n}{d}\cdot\frac{1}{d+1})$

###### Proof.

The number of vertices in $Hasse_{d}(\Delta^{n})$ is
$|V(Hasse_{d}(\Delta^{n}))|=\binom{n}{d}+\binom{n}{d+1}$. As $n\geq 2d+1$, the
maximum degree of $Hasse_{d}(\Delta^{n})$ is $d_{\max}=n-d$. We plug these
values and the lower bound on $EE(Hasse_{d}(\Delta^{n}))$ into the equation
given by Corollary 7.6 to obtain a lower bound on
$\operatorname{tw}(Hasse_{d}(\Delta^{n}))$.

$\displaystyle\operatorname{tw}(Hasse_{d}(\Delta^{n}))$
$\displaystyle\geq\frac{EE(Hasse_{d}(\Delta^{n}))\cdot|V(Hasse_{d}(\Delta^{n}))|}{4\cdot
d_{\max}}$ $\displaystyle\geq\frac{\binom{n}{d}+\binom{n}{d+1}}{4\cdot
4\cdot(n-d)}$ $\displaystyle\geq\frac{\binom{n}{d+1}}{4\cdot 4\cdot(n-d)}$

We can derive the equality
$\binom{n}{d+1}\cdot\frac{1}{n-d}=\binom{n}{d}\cdot\frac{1}{d+1}$ by expanding
$\binom{n}{d+1}$, which gives the theorem statement. ∎

##  8 Acknowledgements

We would like to thank Nello Blaser and Erlend Raa Vȧgset for helpful
discussions about Section 7, specifically for helping us prove Theorem 7.2.

## References

  * [1] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski.  Complexity of finding embeddings in a k-tree.  SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987\.
  * [2] László Babai and Mario Szegedy.  Local expansion of symmetrical graphs.  Combinatorics, Probability and Computing, 1(1):1–11, 1992.
  * [3] Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer.  Efficient Algorithms to Decide Tightness.  In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [4] Nello Blaser, Morten Brun, Lars M. Salbu, and Erlend Raa Vågset.  The parameterized complexity of finding minimum bounded chains, 2021.
  * [5] Nello Blaser and Erlend Raa Vågset.  Homology localization through the looking-glass of parameterized complexity theory, 2020.
  * [6] Hans Bodlaender, Pål G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk.  A $O(c^{k}n)$ 5-approximation algorithm for treewidth, 2013.
  * [7] Glencora Borradaile, William Maxwell, and Amir Nayyeri.  Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes.  In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [8] Benjamin Burton and Rodney Downey.  Courcelle’s theorem for triangulations.  Journal of Combinatorial Theory, Series A, 146, 03 2014.
  * [9] Benjamin A. Burton, Thomas Lewiner, João Paixão, and Jonathan Spreer.  Parameterized complexity of discrete Morse theory.  ACM Transactions on Mathematical Software, 42(1):1–24, Mar 2016\.
  * [10] Benjamin A. Burton and Jonathan Spreer.  The complexity of detecting taut angle structures on triangulations.  Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2013.
  * [11] Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang.  Annotating simplices with a homology basis and its applications.  In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory – SWAT 2012, pages 189–200, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [12] J. Carvalho, Mikael Vejdemo-Johansson, Danica Kragic, and Florian Pokorny.  An algorithm for calculating top-dimensional bounding chains.  PeerJ Computer Science, 4:e153, 05 2018.
  * [13] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri.  Minimum cuts and shortest homologous cycles.  In Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, SCG ’09, page 377–385, New York, NY, USA, 2009. Association for Computing Machinery.
  * [14] Erin Wolf Chambers and Mikael Vejdemo-Johansson.  Computing minimum area homologies.  Computer Graphics Forum, 34(6):13–21, 2014.
  * [15] L.Sunil Chandran and C.R. Subramanian.  Girth and treewidth.  Journal of Combinatorial Theory, Series B, 93(1):23–32, 2005.
  * [16] 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.
  * [17] David Cohen-Steiner, André Lieutier, and Julien Vuillamy.  Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations.  In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [18] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer International Publishing, 2015.
  * [19] Tamal K. Dey.  Efficient algorithms to detect null-homologous cycles on 2-manifolds.  International Journal of Computational Geometry & Applications, 07(03):167–174, 1997.
  * [20] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy.  Optimal homologous cycles, total unimodularity, and linear programming.  SIAM Journal on Computing, 40(4):1026–1044, 2011.
  * [21] Reinhard Diestel.  Graph Theory (Graduate Texts in Mathematics).  Springer, August 2005.
  * [22] Nathan M. Dunfield and Anil N. Hirani.  The least spanning area of a knot and the optimal bounding chain problem.  In Proceedings of the 27th Annual Symposium on Computational Geometry, SCG’11, Proceedings of the Annual Symposium on Computational Geometry, pages 135–144, July 2011.  27th Annual ACM Symposium on Computational Geometry, SCG’11 ; Conference date: 13-06-2011 Through 15-06-2011.
  * [23] Jeff Erickson and Amir Nayyeri.  Minimum cuts and shortest non-separating cycles via homology covers.  In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1166–1176, 2011.