# Revisiting the Complexity of and Algorithms for the Graph Traversal Edit
Distance and Its Variants

Yutong Qiu These authors contributed equally to this work. Computational
Biology Department, School of Computer Science,
Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA  Yihang
Shen00footnotemark: 0 Computational Biology Department, School of Computer
Science,
Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA  Carl Kingsford
To whom correspondence should be addressed<EMAIL_ADDRESS>Computational
Biology Department, School of Computer Science,
Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA

###### Abstract

The graph traversal edit distance (GTED), introduced by Ebrahimpour Boroojeny
et al. (2018), is an elegant distance measure defined as the minimum edit
distance between strings reconstructed from Eulerian trails in two edge-
labeled graphs. GTED can be used to infer evolutionary relationships between
species by comparing de Bruijn graphs directly without the computationally
costly and error-prone process of genome assembly. Ebrahimpour Boroojeny et
al. (2018) propose two ILP formulations for GTED and claim that GTED is
polynomially solvable because the linear programming relaxation of one of the
ILPs always yields optimal integer solutions. The claim that GTED is
polynomially solvable is contradictory to the complexity results of existing
string-to-graph matching problems.

We resolve this conflict in complexity results by proving that GTED is NP-
complete and showing that the ILPs proposed by Ebrahimpour Boroojeny et al. do
not solve GTED but instead solve for a lower bound of GTED and are not
solvable in polynomial time. In addition, we provide the first two, correct
ILP formulations of GTED and evaluate their empirical efficiency. These
results provide solid algorithmic foundations for comparing genome graphs and
point to the direction of heuristics.
The source code to reproduce experimental results is available at
https://github.com/Kingsford-Group/gtednewilp/.

##  1 Introduction

Graph traversal edit distance (GTED) [1] is an elegant measure of the
similarity between the strings represented by edge-labeled Eulerian graphs.
For example, given two de Bruijn assembly graphs [2], computing GTED between
them measures the similarity between two genomes without the computationally
intensive and possibly error-prone process of assembling the genomes. Using an
approximation of GTED between assembly graphs of Hepatitis B viruses,
Ebrahimpour Boroojeny et al. [1] group the viruses into clusters consistent
with their taxonomy. This can be extended to inferring phylogeny relationships
in metagenomic communities or comparing heterogeneous disease samples such as
cancer. There are several other methods to compute a similarity measure
between strings encoded by two assembly graphs [3, 4, 5, 6]. GTED has the
advantage that it does not require prior knowledge on the type of the genome
graph or the complete sequence of the input genomes. The input to the GTED
problem is two unidirectional, edge-labeled Eulerian graphs, which are defined
as:

######  Definition 1 (Unidirectional, edge-labeled Eulerian Graph).

A unidirectional, edge-labeled Eulerian graph is a connected directed graph
$G=(V,E,\ell,\Sigma)$, with node set $V$, edge multi-set $E$, constant-size
alphabet $\Sigma$, and single-character edge labels $\ell:E\rightarrow\Sigma$,
such that $G$ contains an Eulerian trail that traverses every edge $e\in E$
exactly once. The unidirectional condition means that all edges between the
same pair of nodes are in the same direction.

Such graphs arise in genome assembly problems (e.g. the de Bruijn subgraphs).
Computing GTED is the problem of computing the minimum edit distance between
the two most similar strings represented by Eulerian trails each input graph.

######  Problem 1 (Graph Traversal Edit Distance (GTED) [1]).

Given two unidirectional, edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$,
compute

$\textsc{GTED}(G_{1},G_{2})\triangleq\min_{\begin{subarray}{c}t_{1}\in\textrm{trails}(G_{1})\\\
t_{2}\in\textrm{trails}(G_{2})\end{subarray}}\textrm{edit}(\textrm{str}(t_{1}),\textrm{str}(t_{2})).$
(1)

Here, $\textrm{trails}(G)$ is the collection of all Eulerian trails in graph
$G$, $\textrm{str}(t)$ is a string constructed by concatenating labels on the
Eulerian trail $t=(e_{0},e_{1},\dots,e_{n})$, and $\textrm{edit}(s_{1},s_{2})$
is the edit distance between strings $s_{1}$ and $s_{2}$.

Ebrahimpour Boroojeny et al. [1] claim that GTED is polynomially solvable by
proposing an integer linear programming (ILP) formulation of GTED and arguing
that the constraints of the ILP make it polynomially solvable. This result,
however, conflicts with several complexity results on string-to-graph matching
problems. Kupferman and Vardi [7] show that it is NP-complete to determine if
a string exactly matches an Eulerian tour in an edge-labeled Eulerian graph.
Additionally, Jain et al. [8] show that it is NP-complete to compute an edit
distance between a string and strings represented by a labeled graph if edit
operations are allowed on the graph. On the other hand, polynomial-time
algorithms exist to solve string-to-string alignment [9] and string-to-graph
alignment [8] when edit operations on graphs are not allowed.

We resolve the conflict among the results on complexity of graph comparisons
by revisiting the complexity of and the proposed solutions to GTED. We prove
that computing GTED is NP-complete by reducing from the Hamiltonian Path
problem, reaching an agreement with other related results on complexity.
Further, we point out with a counter-example that the optimal solution of the
ILP formulation proposed by Ebrahimpour Boroojeny et al. [1] does not solve
GTED.

We give two ILP formulations for GTED. The first ILP has an exponential number
of constraints and can be solved by subtour elimination iteratively [10, 11].
The second ILP has a polynomial number of constraints and shares a similar
high-level idea of the global ordering approach [11] in solving the Traveling
Salesman problem [12].

In Qiu and Kingsford [13], Flow-GTED (FGTED), a variant of GTED is proposed to
compare two sets of strings instead of two strings encoded by graphs. FGTED is
equal to the edit distance between the most similar sets of strings spelled by
the decomposition of flows between a pair of predetermined source and sink
nodes. The similarity between the sets of strings reconstructed from the flow
decomposition is measured by the Earth Mover’s Edit Distance [14, 13]. FGTED
is used to compare pan-genomes, where both the frequency and content of
strings are essential to represent the population of organisms. Qiu and
Kingsford [13] reduce FGTED to GTED, and via the claimed polynomial-time
algorithm of GTED, argue that FGTED is also polynomially solvable. We show
that this claim is false by proving that FGTED is also NP-complete.

While the optimal solution to ILP proposed in Ebrahimpour Boroojeny et al. [1]
does not solve GTED, it does compute a lower bound to GTED. We characterize
the cases when GTED is equal to this lower bound. In addition, we point out
that solving this ILP formulation finds a minimum-cost matching between
closed-trail decompositions in the input graphs, which may be used to compute
the similarity between repeats in the genomes. Ebrahimpour Boroojeny et al.
[1] claim their proposed ILP formulation is solvable in polynomial time by
arguing that the constraint matrix of the linear relaxation of the ILP is
always totally unimodular. We show that this claim is false by proving that
the constraint matrix is not always totally unimodular and showing that there
exists optimal fractional solutions to its linear relaxation.

We evaluate the efficiency of solving ILP formulations for GTED and its lower
bound on simulated genomic strings and show that it is impractical to compute
GTED on larger genomes.

In summary, we revisit two important problems in genome graph comparisons:
Graph Traversal Edit Distance (GTED) and its variant FGTED. We show that both
GTED and FGTED are NP-complete, and provide the first correct ILP formulations
for GTED. We also show that the ILP formulation proposed by [1] is a lower
bound to GTED. We evaluate the efficiency of the ILPs for GTED and its lower
bound on genomic sequences. These results provide solid algorithmic
foundations for continued algorithmic innovation on the task of comparing
genome graphs and point to the direction of approximation heuristics.

##  2 GTED and FGTED are NP-complete

###  2.1 Conflicting results on computational complexity of GTED and string-
to-graph matching

The natural decision versions of all of the computational problems described
above and below are clearly in NP. Under the assumption that
$\textrm{P}\neq\textrm{NP}$, the results on the computational complexity of
GTED and string-to-graph matching claimed in Ebrahimpour Boroojeny et al. [1]
and Kupferman and Vardi [7], respectively, cannot be both true.

Kupferman and Vardi [7] show that the problem of determining if an input
string can be spelled by concatenating edge labels in an Eulerian trail in an
input graph is NP-complete. We call this problem Eulerian Trail Equaling Word.
We show in Theorem 1 that we can reduce ETEW to GTED, and therefore if GTED is
polynomially solvable, then ETEW is polynomially solvable. The complete proof
is in Appendix A.1.

######  Problem 2 (Eulerian Trail Equaling Word [7]).

Given a string $s\in\Sigma^{*}$, an edge-labaled Eulerian graph $G$, find an
Eulerian trail $t$ of $G$ such that $\textrm{str}(t)=s$.

######  Theorem 1.

If $\textsc{GTED}\in\textrm{P}$ then $\textsc{ETEW}\in\textrm{P}$.

###### Proof sketch.

We first convert an input instance $\langle s,G\rangle$ to ETEW into an input
instance $\langle G_{1},G_{2}\rangle$ to GTED by (a) creating graph $G_{1}$
that only contains edges that reconstruct string $s$ and (b) modifying $G$
into $G_{2}$ by extending the anti-parallel edges so that $G_{2}$ is
unidirectional. We show that if $\textsc{GTED}(G_{1},G_{2})=0$, there must be
an Eulerian trail in $G$ that spells $s$, and if
$\textsc{GTED}(G_{1},G_{2})>0$, $G$ must not contain an Eulerian trail that
spells $s$. ∎

Hence, an (assumed) polynomial-time algorithm for GTED solves ETEW in
polynomial time. This contradicts Theorem 6 of Kupferman and Vardi [7] of the
NP-completeness of ETEW (under $\textrm{P}\neq\textrm{NP}$).

###  2.2 Reduction from Hamiltonian Path to GTED and FGTED

We resolve the contradiction by showing that GTED is NP-complete. The details
of the proof are in Appendix A.2.

######  Theorem 2.

GTED is NP-complete.

###### Proof sketch.

We reduce from the Hamiltonian Path problem, which asks whether a directed,
simple graph $G$ contains a path that visits every vertex exactly once. Here
simple means no self-loops or parallel edges. The reduction is almost
identical to that presented in Kupferman and Vardi [7], and from here until
noted later in the proof the argument is identical except for the
technicalities introduced to force unidirectionality (and another minor change
described later).

Let $\langle G=(V,E)\rangle$ be an instance of Hamiltonian Path, with $n=|V|$
vertices. We first create the Eulerian closure of $G$, which is defined as
$G^{\prime}=(V^{\prime},E^{\prime})$ where

$V^{\prime}=\\{v^{in},v^{out}:v\in V\\}\cup\\{w\\}.$ (2)

Here, each vertex in $V$ is split into $v^{in}$ and $v^{out}$, and $w$ is a
newly added vertex. $E^{\prime}$ is the union of the following sets of edges
and their labels:

  * •

$E_{1}=\\{(v^{in},v^{out}):v\in V\\}$, labeled a,

  * •

$E_{2}=\\{(u^{out},v^{in}):(u,v)\in E\\}$, labeled b,

  * •

$E_{3}=\\{(v^{out},v^{in}):v\in V\\}$, labeled c,

  * •

$E_{4}=\\{(v^{in},u^{out}):(u,v)\in E\\}$, labeled c,

  * •

$E_{5}=\\{(u^{in},w):u\in V\\}$, labeled c,

  * •

$E_{6}=\\{(w,u^{in}):u\in V\\}$, labeled b.

$G^{\prime}$ is an Eulerian graph by construction but contains anti-parallel
edges. We further create $G^{\prime\prime}$ from $G^{\prime}$ by adding dummy
nodes so that each pair of antiparallel edges is split into two parallel,
length-2 paths with labels x#, where x is the original label.

We also create a graph $C$ that has the same number of edges as
$G^{\prime\prime}$ and spells out a string

$q=\texttt{a\\#}(\texttt{b\\#a\\#})^{n-1}(\texttt{c\\#})^{2n-1}(\texttt{c\\#b\\#})^{|E|+1}.$
(3)

We then argue that $G$ has a Hamiltonian path if and only if
$G^{\prime\prime}$ spells out the string $q$, which uses the same line of
arguments and graph traversals as in Kupferman and Vardi [7]. We then show
that $\textsc{GTED}(G^{\prime\prime},C)=0$ if and only if $G^{\prime\prime}$
spells $q$. ∎

Following a similar argument, we show that FGTED is also NP-complete, and its
proof is in Appendix A.3.

######  Theorem 3.

FGTED is NP-complete.

##  3 Revisiting the correctness of the proposed ILP solutions to GTED

In this section, we revisit two proposed ILP solutions to GTED by Ebrahimpour
Boroojeny et al. [1] and show that the optimal solution to these ILP is not
always equal to GTED.

###  3.1 Alignment graph

The previously proposed ILP formulations for GTED are based on the alignment
graph constructed from input graphs. The high-level concept of an alignment
graph is similar to the dynamic programming matrix for the string-to-string
alignment problem [9].

Figure 1: (a) An example of two edge labeled Eulerian graphs $G_{1}$ (top) and
$G_{2}$ (bottom). (b) The alignment graph $\mathcal{A}(G_{1},G_{2})$. The
cycle with red edges is the path corresponding to
$\textsc{GTED}(G_{1},G_{2})$. Red solid edges are matches with cost 0 and red
dashed-line edge is mismatch with cost 1.

######  Definition 2 (Alignment graph).

Let $G_{1},\leavevmode\nobreak\ G_{2}$ be two unidirectional, edge-labeled
Eulerian graphs. The _alignment graph_ $\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$
is a directed graph that has vertex set $V=V_{1}\times V_{2}$ and edge multi-
set $E$ that equals the union of the following:

Vertical edges

$[(u_{1},u_{2}),(v_{1},u_{2})]$ for $(u_{1},v_{1})\in E_{1}$ and $u_{2}\in
V_{2}$,

Horizontal edges

$[(u_{1},u_{2}),(u_{1},v_{2})]$ for $u_{1}\in V_{1}$ and $(u_{2},v_{2})\in
E_{2}$,

Diagonal edges

$[(u_{1},u_{2}),(v_{1},v_{2})]$ for $(u_{1},v_{1})\in E_{1}$ and
$(u_{2},v_{2})\in E_{2}$.

Each edge is associated with a cost by the cost function
$\delta:E\rightarrow\mathbb{R}$.

Each diagonal edge $e=[(u_{1},v_{1}),(u_{2},v_{2})]$ in an alignment graph can
be projected to $(u_{1},v_{1})$ and $(u_{2},v_{2})$ in $G_{1}$ and $G_{2}$,
respectively. Similarly, each vertical edge can be projected to one edge in
$G_{1}$, and each horizontal edge can be projected to one edge in $G_{2}$.

We define the edge projection function $\pi_{i}$ that projects an edge from
the alignment graph to an edge in the input graph $G_{i}$. We also define the
path projection function $\Pi_{i}$ that projects a trail in the alignment
graph to a trail in the input graph $G_{i}$. For example, let a trail in the
alignment graph be $p=(e_{1},e_{2},\dots,e_{m})$, and
$\Pi_{i}(p)=(\pi_{i}(e_{1}),\pi_{i}(e_{2}),\dots,\pi_{i}(e_{m}))$ is a trail
in $G_{i}$.

An example of an alignment graph is shown in Figure 1(b). The horizontal edges
correspond to gaps in strings represented by $G_{1}$, vertical edges
correspond to gaps in strings represented by $G_{2}$, and diagonal edges
correspond to the matching between edge labels from the two graphs. In the
rest of this paper, we assume that the costs for horizontal and vertical edges
are 1, and the costs for the diagonal edges are 1 if the diagonal edge
represents a mismatch and 0 if it is a match. The cost function $\delta$ can
be defined to capture the cost of matching between edge labels or inserting
gaps. This definition of alignment graph is also a generalization of the
alignment graph used in string-to-graph alignment [8].

###  3.2 The first previously proposed ILP for GTED

Lemma 1 in Ebrahimpour Boroojeny et al. [1] provides a model for computing
GTED by finding the minimum-cost trail in the alignment graph. We reiterate it
here for completeness.

######  Lemma 1 ([1]).

For any two edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$,

$\displaystyle\textsc{GTED}(G_{1},G_{2})=\textrm{minimize}_{c}$
$\displaystyle\delta(c)$ (4) subject to $\displaystyle c\text{ is a trail in
}\mathcal{A}(G_{1},G_{2}),$ $\displaystyle\Pi_{i}(c)\text{ is an Eulerian
trail in }G_{i}\text{ for }i=1,2,$

where $\delta(c)$ is the total edge cost of $c$, and $\Pi_{i}(c)$ is the
projection from $c$ to $G_{i}$.

An example of such a minimum-cost trail is shown in Figure 1(b). Ebrahimpour
Boroojeny et al. [1] provide the following ILP formulation and claim that it
is a direct translation of Lemma 1:

$\displaystyle\underset{x\in\mathbb{N}^{|E|}}{\textrm{minimize}}\quad$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (5) subject to $\displaystyle Ax=0$
(6) $\displaystyle\sum_{e\in E}x_{e}I_{i}(e,f)=1\quad\text{for }i=1,2\text{
and for all }f\in E_{i}$ (7) $\displaystyle
A_{ue}=\begin{cases}-1\quad\text{if $e=(u,v)\in E$ for some vertex $v\in
V$}\\\ 1\quad\text{if $e=(v,u)\in E$ for some $u\in V$}\\\
0\quad\text{otherwise}\end{cases}$ (8)

Here, $E$ is the edge set of $\mathcal{A}(G_{1},G_{2})$. $A$ is the negative
incidence matrix of size $|V|\times|E|$, and $I_{i}(e,f)$ is an indicator
function that is 1 if edge $e$ in $E$ projects to edge $f$ in the input graph
$G_{i}$ (and 0 otherwise). We define the domain of each $x_{e}$ to include all
non-negative integers. However, due to constraints (7), the values of $x_{e}$
are limited to either 0 or 1. We describe this ILP formulation with the
assumption that both input graphs have closed Eulerian trails, which means
that each node has equal numbers of incoming and outgoing edges. We discuss
the cases when input graphs contain open Eulerian trails in Section 4.

While the ILP in (5)-(8) allows the solutions to select disjoint cycles in the
alignment graph, the projection of edges in these disjoint cycles does not
correspond to a single string represented by either of the input graphs. We
show that the ILP in (5)-(8) does not solve GTED by giving an example where
the objective value of the optimal solution to the ILP in (5)-(8) is not equal
to GTED.

Figure 2:  (a) The subgraph in the alignment graph induced by an optimal
solution to the ILP in (5)-(8) and the ILP in (11)-(12) with input graphs on
the left and top. The red and blue edges in the alignment graph are edges
matching labels in red and blue font, respectively, and are part of the
optimal solution to the ILP in (5)-(8). The cost of the red and blue edges are
zero. (b) The subgraph induced by $x^{init}$ with $s_{1}=u_{1}$ and
$s_{2}=v_{1}$ according to the ILP in (11)-(12). The rest of the edges in the
alignment graph are omitted for simplicity.

Construct two input graphs as shown in Figure 2(a). Specifically, $G_{1}$
spells circular permutations of TTTGAA and $G_{2}$ spells circular
permutations of TTTAGA. It is clear that $\textsc{GTED}(G_{1},G_{2})=2$ under
Levenshtein edit distance. On the other hand, as shown in Figure 2(a), an
optimal solution in $\mathcal{A}(G_{1},G_{2})$ contains two disjoint cycles
with nonzero $x_{e}$ values that have a total edge cost equal to 0. This
solution is a feasible solution to the ILP in (5)-(8). It is also an optimal
solution because the objective value is zero, which is the lower bound on the
ILP in (5)-(8). This optimal objective value, however, is smaller than
$\textsc{GTED}(G_{1},G_{2})$. Therefore, the ILP in (5)-(8) does not solve
GTED since it allows the solution to be a set of disjoint components.

###  3.3 The second previously proposed ILP formulation of GTED

We describe the second proposed ILP formulation of GTED by Ebrahimpour
Boroojeny et al. [1]. Following Ebrahimpour Boroojeny et al. [1], we use
simplices, a notion from geometry, to generalize the notion of an edge to
higher dimensions. A $k$-simplex is a $k$-dimensional polytope which is the
convex hull of its $k+1$ vertices. For example, a $1$-simplex is an undirected
edge, and a $2$-simplex is a triangle. We use the orientation of a simplex,
which is given by the ordering of the vertex set of a simplex up to an even
permutation, to generalize the notion of the edge direction [15, p. 26]. We
use square brackets $[\cdot]$ to denote an oriented simplex. For example,
$[v_{0},v_{1}]$ denotes a 1-simplex with orientation $v_{0}\rightarrow v_{1}$,
which is a directed edge from $v_{0}$ to $v_{1}$, and $[v_{0},v_{1},v_{2}]$
denotes a 2-simplex with orientation corresponding to the vertex ordering
$v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow v_{0}$. Each $k$-simplex
has two possible unique orientations, and we use the signed coefficient to
connect their forms together, e.g. $[v_{0},v_{1}]=-[v_{1},v_{0}]$.

Figure 3: (a) A graph that contains an unoriented 2-simplex with three
unoriented 1-simplices. (b), (c) The same graph with two different ways of
orienting the simplices and the corresponding boundary matrices.

For each pair of graphs $G_{1}$ and $G_{2}$ and their alignment graph
$\mathcal{A}(G_{1},G_{2})$, we define an oriented $2$-simplex set
$T(G_{1},G_{2})$ which is the union of:

  * •

$[(u_{1},u_{2}),(v_{1},u_{2}),(v_{1},v_{2})]$ for all $(u_{1},v_{1})\in E_{1}$
and $(u_{2},v_{2})\in E_{2}$, or

  * •

$[(u_{1},u_{2}),(u_{1},v_{2}),(v_{1},v_{2})]$ for all $(u_{1},v_{1})\in E_{1}$
and $(u_{2},v_{2})\in E_{2}$,

We use the boundary operator [15, p. 28], denoted by $\partial$, to map an
oriented $k$-simplex to a sum of oriented $(k-1)$-simplices with signed
coefficients.

$\displaystyle\partial[v_{0},v_{1},\dots,v_{k}]=\sum_{i=0}^{p}(-1)^{i}[v_{0},\dots,\hat{v_{i}},\dots,v_{k}],$
(9)

where $\hat{v_{i}}$ denotes the vertex $v_{i}$ is to be deleted. Intuitively,
the boundary operator maps the oriented $k$-simplex to a sum of oriented
$(k-1)$-simplices such that their vertices are in the $k$-simplex and their
orientations are consistent with the orientation of the $k$-simplex. For
example, when $k=2$, we have:

$\displaystyle\partial[v_{0},v_{1},v_{2}]=[v_{1},v_{2}]-[v_{0},v_{2}]+[v_{0},v_{1}]=[v_{1},v_{2}]+[v_{2},v_{0}]+[v_{0},v_{1}].$
(10)

We reiterate the second ILP formulation proposed in Ebrahimpour Boroojeny et
al. [1]. Given an alignment graph $\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$ and
the oriented 2-simplex set $T(G_{1},G_{2})$,

$\displaystyle\underset{x\in\mathbb{N}^{|E|},y\in\mathbb{Z}^{|T(G_{1},G_{2})|}}{\textrm{minimize}}$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (11) subject to $\displaystyle
x=x^{init}+[\partial]y$

Entries in $x$ and $y$ correspond to 1-simplices and 2-simplices in $E$ and
$T(G_{1},G_{2})$, respectively. $[\partial]$ is a $|E|\times|T(G_{1},G_{2})|$
boundary matrix where each entry $[\partial]_{i,j}$ is the signed coefficient
of the oriented 1-simplex (the directed edge) in $E$ corresponding to $x_{i}$
in the boundary of the oriented 2-simplex in $T(G_{1},G_{2})$ corresponding to
$y_{j}$. The index $i,j$ for each 1-simplex or 2-simplex is assigned based on
an arbitrary ordering of the 1-simplices in $E$ or the 2-simplices in
$T(G_{1},G_{2})$. An example of the boundary matrix is shown in Figure 3.
$\delta(e)$ is the cost of each edge. $x^{init}\in\mathbb{R}^{|E|}$ is a
vector where each entry corresponds to a 1-simplex in $E$ with
$|E_{1}|+|E_{2}|$ nonzero entries that represent one Eulerian trail in each
input graph. $x^{init}$ is a feasible solution to the ILP. Let $s_{1}$ be the
source of the Eulerian trail in $G_{1}$, and $s_{2}$ be the sink of the
Eulerian trail in $G_{2}$. Each entry in $x^{init}$ is defined by

$\displaystyle x_{e}^{init}=\begin{cases}1\quad&\text{if}\leavevmode\nobreak\
e=[(u_{1},s_{2}),(v_{1},s_{2})]\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ e=[(s_{1},u_{2}),(s_{1},v_{2})],\\\
0\quad&\text{otherwise}.\end{cases}$ (12)

If the Eulerian trail is closed in $G_{i}$, $s_{i}$ can be any vertex in
$V_{i}$. An example of $x^{init}$ is shown in Figure 2(b).

We provide a complete proof in Section B of the Appendix that the ILP in
(5)-(8) is equivalent to the ILP in (11)-(12). Therefore, the example we
provided in Section 3.2 is also an optimal solution to the ILP in (11)-(12)
but not a solution to GTED. Thus, the ILP in (11)-(12) does not always solve
GTED.

##  4 New ILP solutions to GTED

Figure 4: Modified alignment graphs based on input types. (a) $G_{1}$ has open
Eulerian trails while $G_{2}$ has closed Eulerian trails. (b) Both $G_{1}$ and
$G_{2}$ have closed Eulerian trails. (c) Both $G_{1}$ and $G_{2}$ have open
Eulerian trails. Solid red and blue nodes are the source and sink nodes of the
graphs with open Eulerian trails. “s” and “t” are the added source and sink
nodes. Colored edges are added alignment edges directing from and to source
and sink nodes, respectively.

To ensure that our new ILP formulations are applicable to input graphs
regardless of whether they contain an open or closed Eulerian trail, we add a
source node $s$ and a sink node $t$ to the alignment graph. Figure 4
illustrates three possible cases of input graphs.

  1. 1.

If only one of the input graphs has closed Eulerian trails, wlog, let $G_{1}$
be the input graph with open Eulerian trails. Let $a_{1}$ and $b_{1}$ be the
start and end of the Eulerian trail that have odd degrees. Add edges
$[s,(a_{1},v_{2})]$ and $[(b_{1},v_{2}),t]$ to $E$ for all nodes $v_{2}\in
V_{2}$ (Figure 4(a)).

  2. 2.

If both input graphs have closed Eulerian trails, let $a_{1}$ and $a_{2}$ be
two arbitrary nodes in $G_{1}$ and $G_{2}$, respectively. Add edges
$[s,(a_{1},v_{2})]$, $[s,(v_{1},a_{2})]$, $[(a_{1},v_{2}),t]$ and
$[(v_{1},a_{2}),t]$ for all nodes $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$ to $E$
(Figure 4(b)).

  3. 3.

If both input graphs have open Eulerian trails, add edges $[s,(a_{1},a_{2})]$
and $[t,(b_{1},b_{2})]$, where $a_{i}$ and $b_{i}$ are start and end nodes of
the Eulerian trails in $G_{i}$, respectively (Figure 4(c)).

According to Lemma 1, we can solve $\textsc{GTED}(G_{1},G_{2})$ by finding a
trail in $\mathcal{A}(G_{1},G_{2})$ that satisfies the projection
requirements. This is equivalent to finding a $s$-$t$ trail in
$\mathcal{A}(G_{1},G_{2})$ that satisfies constraints:

$\displaystyle\sum_{(u,v)\in E}x_{uv}I_{i}((u,v),f)=1\quad\text{for all
}(u,v)\in E,f\in G_{i},\leavevmode\nobreak\ u\neq s,\leavevmode\nobreak\ v\neq
t,$ (13)

where $I_{i}(e,f)=1$ if the alignment edge $e$ projects to $f$ in $G_{i}$. An
optimal solution to GTED in the alignment graph must start and end with the
source and sink node because they are connected to all possible starts and
ends of Eulerian trails in the input graphs.

Since a trail in $\mathcal{A}(G_{1},G_{2})$ is a flow network, we use the
following flow constraints to enforce the equality between the number of in-
and out-edges for each node in the alignment graph except the source and sink
nodes.

$\displaystyle\sum_{(s,u)\in E}x_{su}$ $\displaystyle=1$ (14)
$\displaystyle\sum_{(v,t)\in E}x_{vt}$ $\displaystyle=1$ (15)
$\displaystyle\sum_{(u,v)\in E}x_{uv}$ $\displaystyle=\sum_{(v,w)\in
E}x_{vw}\quad\text{for all }v\in V$ (16)

Constraints (13) and (16) are equivalent to constraints (7) and (6),
respectively. Therefore, we rewrite the ILP in (5)-(8) in terms of the
modified alignment graph.

$\displaystyle\underset{x\in\mathbb{N}^{|E|}}{\textrm{minimize}}$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (lower bound ILP) subject to
$\displaystyle\text{constraints\leavevmode\nobreak\
\eqref{cons:projection}--\eqref{cons:balance}}.$

As we show in Section 3.2, constraints (13)-(16) do not guarantee that the ILP
solution is one trail in $\mathcal{A}(G_{1},G_{2})$, thus allowing several
disjoint covering trails to be selected in the solution and fails to model
GTED correctly. We show in Section 5 that the solutions to this ILP is a lower
bound to GTED.

According to Lemma 1 in Dias et al. [11], a subgraph of a directed graph $G$
with source node $s$ and sink node $t$ is a $s$-$t$ trail if and only if it is
a flow network and every strongly connected component (SCC) of the subgraph
has at least one edge outgoing from it. Thus, in order to formulate an ILP for
the GTED problem, it is necessary to devise constraints that prevent disjoint
SCCs from being selected in the alignment graph. In the following, we describe
two approaches for achieving this.

###  4.1 Enforcing one trail in the alignment graph via constraint generation

Section 3.2 of Dias et al. [11] proposes a method to design linear constraints
for eliminating disjoint SCCs, which can be directly adapted to our problem.
Let $\mathcal{C}$ be the collection of all strongly connected subgraphs of the
alignment graph $\mathcal{A}(G_{1},G_{2})$. We use the following constraint to
enforce that the selected edges form one $s$-$t$ trail in the alignment graph:

$\displaystyle\text{If }\sum_{(u,v)\in E(C)}x_{uv}=|E(C)|\text{, then
}\sum_{(u,v)\in\varepsilon^{+}(C)}x_{uv}\geq 1\quad\text{for all
}C\in\mathcal{C},$ (17)

where $E(C)$ is the set of edges in the strongly connected subgraph $C$ and
$\varepsilon^{+}(C)$ is the set of edges $(u,v)$ such that $u$ belongs to $C$
and $v$ does not belong to $C$. $\sum_{(u,v)\in E(C)}x_{uv}=|E(C)|$ indicates
that $C$ is in the subgraph of $\mathcal{A}(G_{1},G_{2})$ constructed by all
edges $(u,v)$ with positive $x_{uv}$, and
$\sum_{(u,v)\in\varepsilon^{+}(C)}x_{uv}\geq 1$ guarantees that there exists
an out-going edge of $C$ that is in the subgraph.

We use the same technique as Dias et al. [11] to linearize the “if-then”
condition in (17) by introducing a new variable $\beta$ for each strongly
connected component:

$\displaystyle\sum_{(u,v)\in E(C)}x_{uv}\geq|E(C)|\beta_{C}\quad\text{for all
}C\in\mathcal{C}$ (18) $\displaystyle\sum_{(u,v)\in
E(C)}x_{uv}-|E(C)|+1-|E(C)|\beta_{C}\leq 0\quad\text{for all }C\in\mathcal{C}$
(19)
$\displaystyle\sum_{(u,v)\in\varepsilon^{+}(C)}x_{uv}\geq\beta_{C}\quad\text{for
all }C\in\mathcal{C}$ (20) $\displaystyle\beta_{C}\in\\{0,1\\}\quad\text{for
all }C\in\mathcal{C}$ (21)

To summarize, given any pair of unidirectional, edge-labeled Eulerian graphs
$G_{1}$ and $G_{2}$ and their alignment graph
$\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$, $\textsc{GTED}(G_{1},G_{2})$ is equal
to the optimal solution of the following ILP formulation:

$\displaystyle\underset{x\in\\{0,1\\}^{|E|}}{\textrm{minimize}}$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (exponential ILP) subject to
constraints (13)–(16) and constraints (18)–(21).

This ILP has an exponential number of constraints as there is a set of
constraints for every strongly connected subgraph in the alignment graph. To
solve this ILP more efficiently, we can use the procedure similar to the
iterative constraint generation procedure in Dias et al. [11]. Initially,
solve the ILP with only constraints (13)-(16). Create a subgraph,
$G^{\prime}$, induced by edges with positive $x_{uv}$. For each disjoint SCC
in $G^{\prime}$ that does not contain the sink node, add constraints (18)-(21)
for edges in the SCC and solve the new ILP. Iterate until no disjoint SCCs are
found in the solution.

Algorithm 1 Iterative constraint generation algorithm to solve (exponential
ILP)

1:Input Two unidirectional, edge-labeled Eulerian graphs and their alignment
graph

2:$\mathcal{C}\leftarrow\emptyset$

3:while true do

4: Solve the ILP (exponential ILP) with $\mathcal{C}$

5: if the ILP variables $x_{uv}$ induce a strongly connected component $C$ not
satisfying (17) then

6: $\mathcal{C}=\mathcal{C}\cup\\{C\\}$

7: else

8: return the optimal ILP value and the corresponding optimal solution $x$

9: end if

10:end while

###  4.2 A compact ILP for GTED with polynomial number of constraints

In the worst cases, the number of iterations to solve (exponential ILP) via
constraint generation is exponential. As an alternative, we introduce a
compact ILP with only a polynomial number of constraints. The intuition behind
this ILP is that we can impose a partially increasing ordering on all the
edges so that the selected edges forms a $s$-$t$ trail in the alignment graph.
This idea is similar to the Miller-Tucker-Zemlin ILP formulation of the
Travelling Salesman problem (TSP) [12].

We add variables $d_{uv}$ that are constrained to provide a partial ordering
of the edges in the $s$-$t$ trail and set the variables $d_{uv}$ to zero for
edges that are not selected in the $s$-$t$ trail. Intuitively, there must
exist an ordering of edges in a $s$-$t$ trail such that for each pair of
consecutive edges $(u,v)$ and $(v,w)$, the difference in their order variable
$d_{uv}$ and $d_{vw}$ is 1. Therefore, for each node $v$ that is not the
source or the sink, if we sum up the order variables for the incoming edges
and outgoing edges respectively, the difference between the two sums is equal
to the number of selected incoming/outgoing edges. Lastly, the order variable
for the edge starting at source is 1, and the order variable for the edge
ending at sink is the number of selected edges. This gives the ordering
constraints as follows:

$\displaystyle\text{If }x_{uv}=0,\text{ then }d_{uv}$
$\displaystyle=0\quad\text{for all }(u,v)\in E$ (22)
$\displaystyle\sum_{(v,w)\in E}d_{vw}-\sum_{(u,v)\in E}d_{uv}$
$\displaystyle=\sum_{(v,w)\in E}x_{vw}\quad\text{for all }v\in
V\setminus\\{s,t\\}$ (23) $\displaystyle\sum_{(s,u)\in E}d_{su}$
$\displaystyle=1$ (24) $\displaystyle\sum_{(v,t)\in E}d_{vt}$
$\displaystyle=\sum_{(u,v)\in E}x_{uv}$ (25)

We enforce that all variables $x_{e}\in\\{0,1\\}$ and $d_{e}\in\mathbb{N}$ for
all $e\in E$.

The “if-then” statement in Equation (22) can be linearized by introducing an
additional binary variable $y_{uv}$ for each edge [16, 11]:

$\displaystyle-x_{uv}-|E|y_{uv}$ $\displaystyle\leq-1$ (26) $\displaystyle
d_{uv}-|E|(1-y_{uv})$ $\displaystyle\leq 0$ (27) $\displaystyle y_{uv}$
$\displaystyle\in\\{0,1\\}.$ (28)

Here, $y_{uv}$ is an indicator of whether $x_{uv}\geq 0$. The coefficient
$|E|$ is the number of edges in the alignment graph and also an upper bound on
the ordering variables. When $y_{uv}=1$, $d_{uv}\leq 0$, and $y_{uv}$ does not
impose constraints on $x_{uv}$. When $y_{uv}=0$, $x_{uv}\geq 1$, and $y_{uv}$
does not impose constraints on $d_{uv}$.

###  4.3 Correctness of (compact ILP) for GTED

To show that the optimal objective value of (compact ILP) is equal to GTED, we
show that the optimal solutions to (compact ILP) always form one connected
component.

######  Lemma 2.

Let $x_{e}$ and $d_{e}$ be ILP variables. Let $G^{\prime}$ be a subgraph of
$\mathcal{A}(G_{1},G_{2})$ that is induced by edges with $x_{e}=1$. If $x_{e}$
and $d_{e}$ satisfy constraints (13)-(25) for all $e\in E$, $G^{\prime}$ is
connected with one trail from $s$ to $t$ that traverses each edge in
$G^{\prime}$ exactly once.

###### Proof.

We prove the lemma in 2 parts: (1) all nodes except $s$ and $t$ in
$G^{\prime}$ have an equal number of in- and out-edges, (2) $G^{\prime}$
contains only one connected component.

The first statement holds because the edges of $G^{\prime}$ form a flow from
$s$ to $t$, and is enforced by constraints (16).

We then show that $G^{\prime}$ does not contain isolated subgraphs that are
not reachable from $s$ or $t$. Due to constraint (16), the only possible
scenario is that the isolated subgraph is strongly connected. Suppose for
contradiction that there is a strongly connected component, $C$, in
$G^{\prime}$ that is not reachable from $s$ or $t$.

The sum of the left hand side of constraint (23) over all vertices in $C$ is

$\displaystyle\sum_{v\in C}\Big{(}\sum_{(u,v)\in C}d_{uv}-\sum_{(v,w)\in
C}d_{vw}\Big{)}$ $\displaystyle=\sum_{v\in C}\sum_{(u,v)\in
C}d_{uv}-\sum_{v\in C}\sum_{(v,w)\in C}d_{vw}$ (29)
$\displaystyle=\sum_{(u,v)\in E(C)}d_{uv}-\sum_{(v,w)\in E(C)}d_{vw}=0.$ (30)

However, the right-hand side of the same constraints is always positive. Hence
we have a contradiction. Therefore, $G^{\prime}$ has only one connected
component. ∎

Due to Lemma 1 and Lemma 2, given input graphs $G_{1}$ and $G_{2}$ and the
alignment graph $\mathcal{A}(G_{1},G_{2})$, $\textsc{GTED}(G_{1},G_{2})$ is
equal to the optimal objective of

$\displaystyle\underset{x\in\\{0,1\\}^{|E|}}{\textrm{minimize}}$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (compact ILP) subject to
constraints (13)–(16), constraints (23)–(25) and constraints (26)–(28).

##  5 Closed-trail Cover Traversal Edit Distance

While the (lower bound ILP) and the ILP in (11)-(12) do not solve GTED, the
optimal solution to these ILPs is a lower bound of GTED. These ILP
formulations also solve an interesting variant of GTED, which is a local
similarity measure between two genome graphs. We call this variant Closed-
trail Cover Traversal Edit Distance (CCTED). In the following, we provide the
formal definition of the CCTED problem and then show that the (lower bound
ILP) is the correct ILP formulation for solving CCTED.

We first introduce the min-cost item matching problem between two multi-sets.
Let two multi-sets of items be $S_{1}$ and $S_{2}$, and, wlog, let
$|S_{1}|\leq|S_{2}|$. Let $c:(S_{1}\cup\\{\epsilon\\})\times
S_{2}\to\mathbb{N}$ be the cost of matching either an empty item $\epsilon$ or
an item in $S_{1}$ with an item in $S_{2}$. Given $S_{1}$, $S_{2}$ and the
cost function $c$, min-cost matching problem finds a matching,
$\mathcal{M}_{c}(S_{1},S_{2})$, such that each item in
$S_{1}\cup\\{\epsilon\\}^{|S_{2}|-|S_{1}|}$ is matched with exactly one
distinct item in $S_{2}$ and the total cost of the matching,
$\sum_{(s_{1},s_{2})\in\mathcal{M}_{c}(S_{1},S_{2})}c(s_{1},s_{2})$, is
minimized.

The min-cost item matching problem is similar to the Earth Mover’s Distance
defined in [17], except that only integral units of items can be matched and
the cost of matching an empty item with another item is not constant. Similar
to the Earth Mover’s Distance, the min-cost item matching problem can be
computed using the ILP formulation of the min-cost max-flow problem [14, 13].
When the cost is the edit distance, the cost to match $\epsilon$ with a string
is equal to the length of the string.

Define traversal edit distance, $edit_{t}(t_{1},t_{2})$ as the edit distance
between the strings constructed from a pair of trails $t_{1}$ and $t_{2}$. In
other words,
$edit_{t}(t_{1},t_{2})=edit(\textrm{str}(t_{1}),\textrm{str}(t_{2}))$. CCTED
is defined as:

######  Problem 3 (Closed-Trail Cover Traversal Edit Distance (CCTED)).

Given two unidirectional, edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$
with closed Eulerian trails, compute

$\textsc{CCTED}(G_{1},G_{2})\triangleq\min_{\begin{subarray}{c}C_{1}\in\textrm{CC}(G_{1}),\\\
C_{2}\in\textrm{CC}(G_{2})\end{subarray}}\sum_{\begin{subarray}{c}(t_{1},t_{2})\in\mathcal{M}_{\textrm{edit}_{t}}(C_{1},C_{2})\end{subarray}}\textrm{edit}(\textrm{str}(t_{1}),\textrm{str}(t_{2})),$
(31)

Here, $\textrm{CC}(G)$ denotes the collection of all possible sets of edge-
disjoint, closed trails in $G$, such that every edge in $G$ belongs to exactly
one of these trails. Each element of $\textrm{CC}(G)$ can be interpreted as a
cover of $G$ using such trails. $\mathcal{M}_{\textrm{edit}_{t}}(C_{1},C_{2})$
is a min-cost matching between two covers using the traversal edit distance as
the cost.

CCTED is likely a more suitable metric comparison between genomes that undergo
large-scale rearrangements. This analogy is to the relationship between the
synteny block comparison [3] and the string edit distance computation, where
the former is more often used in interspecies comparisons and in detecting
segmental duplications [18, 19] and the latter is more often seen in
intraspecies comparisons.

Following similar ideas as Lemma 1, we can compute CCTED by finding a set of
closed trails in the alignment graph such that the total cost of alignment
edges is minimized, and the projection of all edges in the collection of
selected trails is equal to the multi-set of input graph edges.

######  Lemma 3.

For any two edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$,

$\displaystyle\textsc{CCTED}(G_{1},G_{2})=\underset{C}{\textrm{minimize}}\quad$
$\displaystyle\sum_{c\in C}\delta(c)$ (32) subject to $\displaystyle C\text{
is a set of closed trails in }\mathcal{A}(G_{1},G_{2}),$
$\displaystyle\bigcup_{e\in C}\Pi_{i}(e)=E_{i}\quad\text{for }i=1,2,$ (33)

where $C$ is a collection of trails and $\delta(c)$ is the total cost of edges
in trail $c$.

###### Proof.

Given any pair of covers $C_{1}\in\textrm{CC}(G_{1})$ and
$C_{2}\in\textrm{CC}(G_{2})$ and their min-cost matching based on the edit
distance $\mathcal{M}_{\textrm{edit}_{t}}(C_{1},C_{2})$, we can project each
pair of matched closed trailed to a closed trail in the alignment graph. For a
matching between a trail and the empty item $\epsilon$, we can project it to a
closed trail in the alignment graph with all vertical edges if the trail is
from $G_{1}$ or horizontal edges if the trail is from $G_{2}$. The total cost
of the projected edges must be greater than or equal to the objective (32). On
the other hand, every collection of trails $C$ that satisfy constraint (33)
can be projected to a cover in each of the input graphs, and $\sum_{c\in
C}\delta(c)\geq CCTED(G_{1},G_{2})$. Hence equality holds.∎

###  5.1 The ILP formulation for CCTED

We show that the ILP in (5)-(8) proposed by Ebrahimpour Boroojeny et al. [1]
solves CCTED.

######  Theorem 4.

Given two input graphs $G_{1}$ and $G_{2}$, the optimal objective value of the
ILP in (5)-(8) based on $\mathcal{A}(G_{1},G_{2})$ is equal to
$\textsc{CCTED}(G_{1},G_{2})$.

###### Proof.

As shown in the proof of Lemma 3, any pair of edge-disjoint, closed-trail
covers in the input graph can be projected to a set of closed trails in
$\mathcal{A}(G_{1},G_{2})$, which satisfied constraints (6)-(8). The objective
of this feasible solution, which is the total cost of the projected closed
trails, equals CCTED. Therefore, $\textsc{CCTED}(G_{1},G_{2})$ is greater than
or equal to the objective of the ILP in (5)-(8).

Conversely, we can transform any feasible solutions of the ILP in (5)-(8) to a
pair of covers of $G_{1}$ and $G_{2}$. We can do this by transforming one
closed trail at a time from the subgraph of the alignment graph,
$\mathcal{A}^{\prime}$ induced by edges with ILP variable $x_{uv}=1$. Let $c$
be a closed trail in $\mathcal{A}^{\prime}$. Let $c_{1}=\Pi_{1}(c)$ and
$c_{2}=\Pi_{2}(c)$ be two closed trails in $G_{1}$ and $G_{2}$ that are
projected from $c$. We can construct an alignment between
$\textrm{str}(c_{1})$ and $\textrm{str}(c_{2})$ from $c$ by adding match or
insertion/deletion columns for each match or insertion/deletion edges in $c$
accordingly. The cost of the alignment is equal to the total cost of edges in
$c$ by the construction of the alignment graph. We can then remove edges in
$c$ from the alignment graph and edges in $c_{1}$ and $c_{2}$ from the input
graphs, respectively. The remaining edges in $\mathcal{A}^{\prime}$ and
$G_{1}$ and $G_{2}$ still satisfy the constraints (6)-(8). Repeat this process
and we get a total cost of $\sum_{e\in E}x_{e}\delta(e)$ that aligns pairs of
closed trails that form covers of $G_{1}$ and $G_{2}$. This total cost is
greater than or equal to $\textsc{CCTED}(G_{1},G_{2})$. ∎

###  5.2 CCTED is a lower bound of GTED

Since the constraints for (lower bound ILP) are a subset of (exponential ILP),
a feasible solution to (exponential ILP) is always a feasible solution to
(lower bound ILP). Since two ILPs have the same objective function,
$\textsc{CCTED}(G_{1},G_{2})\leq\textsc{GTED}(G_{1},G_{2})$ for any pair of
graphs. Moreover, when the solution to (lower bound ILP) forms only one
connected component, the optimal value of (lower bound ILP) is equal to GTED.

######  Theorem 5.

Let $\mathcal{A}^{\prime}(G_{1},G_{2})$ be the subgraph of
$\mathcal{A}(G_{1},G_{2})$ induced by edges $(u,v)\in E$ with $x^{opt}_{uv}=1$
in the optimal solution to (lower bound ILP). There exists
$\mathcal{A}^{\prime}(G_{1},G_{2})$ that has exactly one connected component
if and only if $c^{opt}=\textsc{GTED}(G_{1},G_{2})$.

###### Proof.

We first show that if $c^{opt}=\textsc{GTED}(G_{1},G_{2})$, then there exists
$\mathcal{A}^{\prime}(G_{1},G_{2})$ that has one connected component. A
feasible solution to (exponential ILP) is always a feasible solution to (lower
bound ILP), and since $c^{opt}=\textsc{GTED}(G_{1},G_{2})$, an optimal
solution to (exponential ILP) is also an optimal solution to (lower bound
ILP), which can induce a subgraph in the alignment graph that only contains
one connected component.

Conversely, if $x^{opt}$ induces a subgraph in the alignment graph with only
one connected component, it satisfies constraints (18)-(21) and therefore is
feasible to the ILP for GTED (exponential ILP). Since
$c^{opt}\leq\textsc{GTED}(G_{1},G_{2})$, this solution must also be optimal
for $\textsc{GTED}(G_{1},G_{2})$. ∎

In practice, we may estimate GTED approximately by the solution to (lower
bound ILP). As we show in Section 6, the time needed to solve (lower bound
ILP) is much less than the time needed to solve GTED. However, in adversarial
cases, $c^{opt}$ could be zero but GTED could be arbitrarily large. We can
determine if the $c^{opt}$ is a lower bound on GTED or exactly equal to GTED
by checking if the subgraph induced by the solution to (lower bound ILP) has
multiple connected components.

###  5.3 NP-completeness of CCTED

We prove that the CCTED problem (Problem 3) is NP-complete by reducing from
the Eulerian Trail Equaling Word problem [7].

######  Theorem 6.

Computing CCTED is NP-complete.

###### Proof.

Let Eulerian graph $G=(V,E,\ell,\Sigma)$ and $s$ be an instance of the
Eulerian Tour Equaling Word problem. Construct two graphs, $G_{1}$ and
$G_{2}$. If $G$ contains open Eulerian trails, add an edge directing from the
sink of the graph to the source of the graph. Let the label of the added edge
be $\\#$ that does not appear in $\Sigma$. Let the modified graph be $G_{1}$.
If $G$ contains closed Eulerian trails, let $G_{1}$ be the same as $G$. Let
$G_{2}$ be a graph that contains one cycle with $|E_{1}|$ edges, where $E_{1}$
is the edge set of $G_{1}$. Assign labels to the edges in $G_{2}$ such that
the cycle in $G_{2}$ spells $s$ if $G$ contains closed Eulerian trails, $s\\#$
otherwise.

If $\textsc{CCTED}(G_{1},G_{2})=0$, $G_{2}$ must contain at least one closed
Eulerian trail that spells some circular permutation of $s\\#$. If CCTED is
not zero, it means that $s$ must not match Eulerian trails in $G$. ∎

##  6 Empirical evaluation of the ILP formulations for GTED and its lower
bound

###  6.1 Implementation of the ILP formulations

We implement the algorithms and ILP formulations for (exponential ILP),
(compact ILP) and (lower bound ILP). In practice, the multi-set of edges of
each input graph may contain many duplicates of edges that have the same start
and end vertices due to repeats in the strings. We reduce the number of
variables and constraints in the implemented ILPs by merging the edges that
share the same start and end nodes and record the multiplicity of each edge.
Each $x$ variable is no longer binary but a non-negative integer that
satisfies the modified projection constraints (13):

$\displaystyle\sum_{(u,v)\in E}x_{uv}I_{i}((u,v),f)=M_{i}(f)\quad\text{for all
}(u,v)\in E,\leavevmode\nobreak\ f\in G_{i},u\neq s,v\neq t,$ (34)

where $M_{i}(f)$ is the multiplicity of edge $f$ in $G_{i}$. Let $C$ be the
strongly connected component in the subgraph induced by positive $x_{uv}$, now
$\sum_{(u,v)\in E(C)}x_{uv}$ is no longer upper bounded by $|E(C)|$.
Therefore, constraints (19) is changed to

$\displaystyle\sum_{(u,v)\in E(C)}x_{uv}-|E(C)|+1-W(C)\beta_{C}\leq
0\quad\text{for all }C\in\mathcal{C},$ (35) $\displaystyle W(C)=\sum_{(u,v)\in
E(C)}\max\left(\sum_{f\in G_{1}}M_{1}(f)I_{1}((u,v),f),\sum_{f\in
G_{2}}M_{2}(f)I_{2}((u,v),f)\right),$

where $W(C)$ is the maximum total multiplicities of edges in the strongly
connected subgraph in each input graph that is projected from $C$.

Likewise, constraints (27) that set the upper bounds on the ordering variables
also need to be modified as the upper bound of the ordering variable $d_{uv}$
for each edge no longer represents the order of one edge but the sum of orders
of copies of $(u,v)$ that are selected, which is at most $|E|^{2}$. Therefore,
constraint (27) is changed to

$\displaystyle d_{uv}-|E|^{2}(1-y_{uv})\leq 0.$ (36)

The rest of the constraints remain unchanged.

We ran all our experiments on a server with 48 cores (96 threads) of Intel(R)
Xeon(R) CPU E5-2690 v3 @ 2.60GHz and 378 GB of memory. The system was running
Ubuntu 18.04 with Linux kernel 4.15.0. We solve all the ILP formulations and
their linear relaxations using the Gurobi solver [20] using 32 threads.

###  6.2 GTED on simulated TCR sequences

We construct 20 de Bruijn graphs with $k=4$ using 150-character sequences
extracted from the V genes from the IMGT database [21]. We solve the linear
relaxation of (compact ILP), (exponential ILP) and (lower bound ILP) and their
linear relaxation on all 190 pairs of graphs. We do not show results for
solving (compact ILP) for GTED on this set of graphs as the running time
exceeds 30 minutes on most pairs of graphs.

To compare the time to solve the ILP formulations when GTED is equal to the
optimal objective of (lower bound ILP), we only include 168 out of 190 pairs
where GTED is equal to the lower bound (GTED is slightly higher than the lower
bound in the remaining 22 pairs). On average, it takes 26 seconds wall-clock
time to solve (lower bound ILP), and 71 seconds to solve (exponential ILP)
using the iterative algorithm. On average, it takes 9 seconds to solve the LP
relaxation of (compact ILP) and 1 second to solve the LP relaxation of (lower
bound ILP). The time to construct the alignment graph for all pairs is less
than 0.2 seconds. The distribution of wall-clock running time is shown in
Figure 5(a). The time to solve (exponential ILP) and (lower bound ILP) is
generally positively correlated with the GTED values (Figure 5(b)). On
average, it takes 7 iterations for the iterative algorithm to find the optimal
solution that induces one strongly connected subgraph (Figure 5(c)).

In summary, it is fastest to compute the lower bound of GTED. Computing GTED
exactly by solving the proposed ILPs on genome graphs of size 150 is already
time consuming. When the sizes of the genome graphs are fixed, the time to
solve for GTED and its lower bound increases as GTED between the two genome
graphs increases. In the case where GTED is equal to its lower bound, the
subgraph induced by some optimal solutions of (lower bound ILP) contains more
than one strongly connected component. Therefore, in order to reconstruct the
strings from each input graph that have the smallest edit distance, we
generally need to obtain the optimal solution to the ILP for GTED. In all
cases, the time to solve the (exponential ILP) is less than the time to solve
the (compact ILP).

Figure 5: (a) The distribution of wall-clock running time for constructing
alignment graphs, solving the ILP formulations for GTED and its lower bound,
and their linear relaxations on the log scale. (b) The relationship between
the time to solve (lower bound ILP), (exponential ILP) iteratively and GTED.
(c) The distribution of the number of iterations to solve exponential ILP. The
box plots in each plot show the median (middle line), the first and third
quantiles (upper and lower boundaries of the box), the range of data within
1.5 inter-quantile range between Q1 and Q3 (whiskers), and the outlier data
points.

###  6.3 GTED on difficult cases

Repeats, such as segmental duplications and translocations [22, 23] in the
genomes increase the complexity of genome comparisons. We simulate such
structures with a class of graphs that contain $n$ simple cycles of which
$n-1$ peripheral cycles are attached to the $n$-th central cycle at either a
node or a set of edges (Figure 6(a)). The input graphs in Figure 2 belong to
this class of graphs that contain 2 cycles. This class of graphs simulates the
complex structural variants in disease genomes or the differences between
genomes of different species.

We generate pairs of 3-cycle graphs with varying sizes and randomly assign
letters from {A,T,C,G} to edges. We compute the lower bound of GTED and GTED
using (lower bound ILP) and (compact ILP), respectively. We denote the lower
bound of GTED computed by solving (lower bound ILP) as $\textsc{GTED}_{l}$. We
group the generated 3-cycle graph pairs based on the value of
$(\textsc{GTED}-\textsc{GTED}_{l})$ and select 20 pairs of graphs randomly for
each $(\textsc{GTED}-\textsc{GTED}_{l})$ value ranging from 1 to 5. The
maximum number of edges in all selected graphs is 32.

We show the difficulty of computing GTED using the iterative algorithm on the
100 selected pairs of 3-cycle graphs. We terminate the ILP solver after 20
minutes. As shown in Figure 6, as the difference between GTED and
$\textsc{GTED}_{l}$ increases, the wall-clock time to solve (exponential ILP)
for GTED increases faster than the time to solve (compact ILP) for GTED. For
pairs on graphs with $(\textsc{GTED}-\textsc{GTED}_{l})=5$, on average it
takes more than 15 minutes to solve (exponential ILP) with more than 500
iterations. On the other hand, it takes an average of 5 seconds to solve
(compact ILP) for GTED and no more than 1 second to solve for the lower bound.
The average time to solve each ILP is shown in Table S1.

In summary, on the class of 3-cycle graphs introduced above, the difficulty to
solve GTED via the iterative algorithm increases rapidly as the gap between
GTED and $\textsc{GTED}_{l}$ increases. Although (exponential ILP) is solved
more quickly than (compact ILP) for GTED when the sequences are long and the
GTED is equal to $\textsc{GTED}_{l}$ (Section 6.2), (compact ILP) may be more
efficient when the graphs contain overlapping cycles such that the gap between
GTED and $\textsc{GTED}_{l}$ is larger.

Figure 6: (a) An example of a 3-cycle graph. Cycle 1 and 2 are attached to
cycle 3. (b) The distribution of wall-clock time to solve the compact ILP and
the iterative exponential ILP on 100 pairs of 3-cycle graphs.

##  7 Conclusion

We point out the contradictions in the result on the complexity of labeled
graph comparison problems and resolve the contradictions by showing that GTED,
as opposed to the results in Ebrahimpour Boroojeny et al. [1], is NP-complete.
On one hand, this makes GTED a less attractive measure for comparing graphs
since it is unlikely that there is an efficient algorithm to compute the
measure. On the other hand, this result better explains the difficulty of
finding a truly efficient algorithm for computing GTED exactly. In addition,
we show that the previously proposed ILP of GTED [1] does not solve GTED and
give two new ILP formulations of GTED.

While the previously proposed ILP of GTED does not solve GTED, it solves for a
lower bound of GTED, and we show that this lower bound can be interpreted as a
more “local” measure, CCTED, of the distance between labeled graphs. Further,
we characterize the LP relaxation of the ILP in (11)-(12) and show that,
contrary to the results in Ebrahimpour Boroojeny et al. [1], the LP in
(11)-(12) does not always yield optimal integer solutions.

As shown previously [1, 13], it takes more than 4 hours to solve (lower bound
ILP) for graphs that represent viral genomes that contain $\approx 3000$ bases
with a multi-threaded LP solver. Likewise, we show that computing GTED using
either (exponential ILP) or (compact ILP) is already slow on small genomes,
especially on pairs of simulated genomes that are different due to segmental
duplications and translations. The empirical results show that it is currently
impossible to solve GTED or its lower bound directly using this approach for
bacterial- or eukaryotic-sized genomes on modern hardware. The results here
should increase the theoretical interest in GTED along the directions of
heuristics or approximation algorithms as justified by the NP-hardness of
finding GTED.

## Acknowledgements

The authors would like to thank the members of the Kingsford Group for their
helpful comments throughout this project, in particular Guillaume Marçais. The
authors thank Marina L Knittel, Jacob M Gilbert, and Cenk Sahinalp for their
insightful discussion on the NP-completeness of CCTED. This work was supported
in part by the US National Science Foundation [DBI-1937540, III-2232121], the
US National Institutes of Health [R01HG012470] and by the generosity of Eric
and Wendy Schmidt by recommendation of the Schmidt Futures program.
Conflict of Interest: C.K. is a co-founder of Ocean Genomics, Inc.

## References

  * Ebrahimpour Boroojeny et al. [2020] Ali Ebrahimpour Boroojeny, Akash Shrestha, Ali Sharifi-Zarchi, Suzanne Renick Gallagher, S. Cenk Sahinalp, and Hamidreza Chitsaz.  Graph traversal edit distance and extensions.  _Journal of Computational Biology_ , 27(3):317–329, 2020.
  * Pevzner et al. [2001] Pavel A Pevzner, Haixu Tang, and Michael S Waterman.  An Eulerian path approach to DNA fragment assembly.  _Proceedings of the National Academy of Sciences of USA_ , 98(17):9748–9753, 2001.
  * Polevikov and Kolmogorov [2019] Evgeny Polevikov and Mikhail Kolmogorov.  Synteny paths for assembly graphs comparison.  In _19th International Workshop on Algorithms in Bioinformatics (WABI 2019)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * Minkin and Medvedev [2020] Ilia Minkin and Paul Medvedev.  Scalable pairwise whole-genome homology mapping of long genomes with Bubbz.  _IScience_ , 23(6):101224, 2020.
  * Mangul and Koslicki [2016] Serghei Mangul and David Koslicki.  Reference-free comparison of microbial communities via de Bruijn graphs.  In _Proceedings of the 7th ACM international conference on bioinformatics, computational biology, and health informatics_ , pages 68–77, 2016\.
  * Huntsman and Rezaee [2015] Steve Huntsman and Arman Rezaee.  De Bruijn entropy and string similarity.  _arXiv preprint arXiv:1509.02975_ , 2015.
  * Kupferman and Vardi [2016] Orna Kupferman and Gal Vardi.  Eulerian paths with regular constraints.  In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, _41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)_ , volume 58 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 62:1–62:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-95977-016-3.
  * Jain et al. [2020] Chirag Jain, Haowen Zhang, Yu Gao, and Srinivas Aluru.  On the complexity of sequence-to-graph alignment.  _Journal of Computational Biology_ , 27(4):640–654, 2020.
  * Needleman and Wunsch [1970] Saul B Needleman and Christian D Wunsch.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  _Journal of Molecular Biology_ , 48(3):443–453, 1970.
  * Dantzig et al. [1954] George Dantzig, Ray Fulkerson, and Selmer Johnson.  Solution of a large-scale traveling-salesman problem.  _Journal of the Operations Research Society of America_ , 2(4):393–410, 1954.
  * Dias et al. [2022] Fernando HC Dias, Lucia Williams, Brendan Mumey, and Alexandru I Tomescu.  Minimum flow decomposition in graphs with cycles using integer linear programming.  _arXiv preprint arXiv:2209.00042_ , 2022.
  * Miller et al. [1960] Clair E Miller, Albert W Tucker, and Richard A Zemlin.  Integer programming formulation of traveling salesman problems.  _Journal of the ACM (JACM)_ , 7(4):326–329, 1960\.
  * Qiu and Kingsford [2022] Yutong Qiu and Carl Kingsford.  The effect of genome graph expressiveness on the discrepancy between genome graph distance and string set distance.  _Bioinformatics_ , 38:i404–i412, 2022.
  * Rubner et al. [2000] Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas.  The Earth Mover’s distance as a metric for image retrieval.  _International Journal of Computer Vision_ , 40(2):99–121, 2000.
  * Munkres [2018] James R Munkres.  _Elements of algebraic topology_.  CRC Press, 2018.
  * Bradley et al. [1977] Stephen P Bradley, Arnoldo C Hax, and Thomas L Magnanti.  _Applied mathematical programming_.  Addison-Wesley, 1977.
  * Pele and Werman [2008] Ofir Pele and Michael Werman.  A linear time histogram metric for improved sift matching.  In _Computer Vision–ECCV 2008: 10th European Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings, Part III 10_ , pages 495–508. Springer, 2008.
  * Bourque et al. [2004] Guillaume Bourque, Pavel A Pevzner, and Glenn Tesler.  Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes.  _Genome Research_ , 14(4):507–516, 2004.
  * Vollger et al. [2022] Mitchell R Vollger, Xavi Guitart, Philip C Dishuck, Ludovica Mercuri, William T Harvey, Ariel Gershman, Mark Diekhans, Arvis Sulovari, Katherine M Munson, Alexandra P Lewis, et al.  Segmental duplications and their variation in a complete human genome.  _Science_ , 376(6588):eabj6965, 2022.
  * Gurobi Optimization, LLC [2023] Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2023.  URL https://www.gurobi.com.
  * Lefranc [2011] Marie-Paule Lefranc.  IMGT, the international ImMunoGeneTics information system.  _Cold Spring Harbor Protocols_ , 2011(6):595–603, 2011.
  * Li et al. [2020] Yilong Li, Nicola D Roberts, Jeremiah A Wala, Ofer Shapira, Steven E Schumacher, Kiran Kumar, Ekta Khurana, Sebastian Waszak, Jan O Korbel, James E Haber, et al.  Patterns of somatic structural variation in human cancer genomes.  _Nature_ , 578(7793):112–121, 2020.
  * Darai-Ramqvist et al. [2008] Eva Darai-Ramqvist, Agneta Sandlund, Stefan Müller, George Klein, Stefan Imreh, and Maria Kost-Alimova.  Segmental duplications and evolutionary plasticity at tumor chromosome break-prone regions.  _Genome Research_ , 18(3):370–379, 2008.
  * Ahujia et al. [1993] Ravindra K Ahujia, Thomas L Magnanti, and James B Orlin.  Network flows: Theory, algorithms and applications.  _New Jersey: Prentice-Hall_ , 1993.
  * Dey et al. [2011] 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.
  * Schrijver [1998] Alexander Schrijver.  _Theory of linear and integer programming_.  John Wiley & Sons, 1998.

##  Appendix A Proofs for the NP-completeness of GTED

###  A.1 Reduction from ETEW to GTED

We provide below the complete proof for Theorem 1.

######  Theorem 1.

If $\textsc{GTED}\in\textrm{P}$ then $\textsc{ETEW}\in\textrm{P}$.

###### Proof.

Let $\langle s,G\rangle$ be an instance of ETEW. Construct a directed, acyclic
graph (DAG), $C$, that has only one path. Let the path in $C$ be
$P=(e_{1},\dots,e_{|s|})$ and the edge label of $e_{i}$ be $s[i]$. Clearly,
$C$ is a unidirectional, edge-labeled Eulerian graph, $P$ is the only Eulerian
trail in $C$, and $str(P)=s$.

For the graph $G=(V_{G},E_{G},\ell_{G},\Sigma)$ from the ETEW instance, which
may not be unidirectional, create another graph $G^{\prime}$ that contains all
of the nodes and edges in $G$ except the anti-parallel edges. Let
$\Sigma_{G^{\prime}}=\Sigma\cup\\{\epsilon\\}$, where $\epsilon$ is a
character that is not in $\Sigma$. For each pair of anti-parallel edges
$(u,v)$ and $(v,u)$ in $G$, add four edges
$(u,w_{1}),(w_{1},v),(v,w_{2}),(w_{2},u)$ by introducing new vertices
$w_{1},w_{2}$ to $G^{\prime}$. Let $\ell_{G^{\prime}}(u,w_{1})=\ell_{G}(u,v)$
and $\ell_{G^{\prime}}(w_{2},u)=\ell_{G}(v,u)$. Let
$\ell_{G^{\prime}}(w_{1},v)=\ell_{G^{\prime}}(v,w_{2})=\epsilon$ for every
newly introduced vertex. $G^{\prime}$ has at most twice the number of edges as
$G$ and is Eulerian and unidirectional.

Define the cost of changing a character from $a$ to $b$ $\text{cost}(a,b)$ for
$a,b\in\Sigma\cup\\{-\\}$ to be 0 if $a=b$ and 1 otherwise. “$-$” is the gap
character indicating an insertion or a deletion. Define
$\text{cost}(a,\epsilon)$ with $a\in\Sigma$ to be 1. Define
$\text{cost}(-,\epsilon)$ to be 0.

Use the (assumed) polynomial-time algorithm for GTED to ask whether
$\textsc{GTED}(C,G^{\prime})\leq 0$ under edit distance $\Sigma$. If yes, then
let $(s_{1},s_{2})$ be the 0-cost alignment of the strings spelled out by the
trails in $C$ and $G^{\prime}$, respectively. The non-gap characters of
$s_{1}$ must spell out $s$ since there is only one Eulerian trail in $C$.
Because the alignment cost is $0$, any $-$ (gap) characters in $s_{1}$ must be
aligned with $\epsilon$ characters in $s_{2}$ and any non-gap characters in
$s_{1}$ must be aligned to the same character in $s_{2}$. The trail in
$G^{\prime}$ that spells $s_{2}$ can be transformed to a trail that spells
$s_{3}$ by collapsing the edges with $\epsilon$ character labels, and
$s_{3}=s_{1}$.

If $\textsc{GTED}(C,G^{\prime})>0$, $G$ must not contain an Eulerian trail
that spells $s$. Otherwise, such a trail could be extended to a trail
introducing some $\epsilon$ characters that could be aligned to $s$ with zero
cost by aligning gaps with $\epsilon$ characters.

Hence, an (assumed) polynomial-time algorithm for GTED solves ETEW in
polynomial time. ∎

###  A.2 Reduction from Hamiltonian Path to GTED

We provide below the complete proof for Theorem 2.

######  Theorem 2.

GTED is NP-complete.

###### Proof.

We reduce from the Hamiltonian Path problem, which asks whether a directed,
simple graph $G$ contains a path that visits every vertex exactly once. Here
simple means no self-loops or parallel edges. Let $\langle G=(V,E)\rangle$ be
an instance of Hamiltonian Path, with $n=|V|$ vertices. The reduction is
almost identical to that presented in Kupferman and Vardi [7], and from here
until noted later in the proof the argument is identical except for the
technicalities introduced to force unidirectionality (and another minor change
described later). The first step is to construct the Eulerian closure of $G$,
which is defined as $G^{\prime}=(V^{\prime},E^{\prime})$ where

$V^{\prime}=\\{v^{in},v^{out}:v\in V\\}\cup\\{w\\},$ (37)

and $E^{\prime}$ is the union of the following sets of edges and their labels:

  * •

$E_{1}=\\{(v^{in},v^{out}):v\in V\\}$, labeled a,

  * •

$E_{2}=\\{(u^{out},v^{in}):(u,v)\in E\\}$, labeled b,

  * •

$E_{3}=\\{(v^{out},v^{in}):v\in V\\}$, labeled c,

  * •

$E_{4}=\\{(v^{in},u^{out}):(u,v)\in E\\}$, labeled c,

  * •

$E_{5}=\\{(u^{in},w):u\in V\\}$, labeled c,

  * •

$E_{6}=\\{(w,u^{in}):u\in V\\}$, labeled b.

Since $G^{\prime}$ is connected and every outgoing edge in $G^{\prime}$ has a
corresponding antiparallel incoming edge, $G^{\prime}$ is Eulerian. It is not
unidirectional, so we further create $G^{\prime\prime}$ from $G^{\prime}$ by
adding dummy nodes to each pair of antiparallel edges and labelling the
length-2 paths so created with x#, where x is the original label of the split
edge (a, b, or c) and # is some new symbol (shared between all the new edges).
We call these length-2 paths introduced to achieve unidirectionality “split
edges”.

We now argue that $G$ has a Hamiltonian path iff $G^{\prime\prime}$ has an
Eulerian trail that spells out

$q=\texttt{a\\#}(\texttt{b\\#a\\#})^{n-1}(\texttt{c\\#})^{2n-1}(\texttt{c\\#b\\#})^{|E|+1}.$
(38)

If such an Eulerian trail exists, then the trail starts with spelling the
string $\texttt{a\\#}(\texttt{b\\#a\\#})^{n-1}$, which corresponds to a
Hamiltonian trail in $G$ since it visits exactly $n$ “vertex split edges”
(type $E_{1}$, labeled a#) and each vertex split edge can be used only once
(since it is an Eulerian trail). Further, successively visited vertices must
be connected by an edge in $G$ since those are the only b# split edges in
$G^{\prime\prime}$ (except those leaving $w$, but $w$ must not be involved in
spelling out $\texttt{a\\#}(\texttt{b\\#a\\#})^{n-1}$, since entering $w$
requires using a split edge labeled c#).

For the other direction, if a $G$ has a Hamiltonian path $v_{1},\dots,v_{n}$,
then walking that sequence of vertices in $G^{\prime\prime}$ will spell out
$\texttt{a\\#}(\texttt{b\\#a\\#})^{n-1}$. This path will cover all $E_{1}$
edges and the $E_{2}$ edges that are on the Hamiltonian path. Retracing the
path so far in reverse will use $2n-1$ split edges labeled c#, consuming the
$(\texttt{c\\#})^{2n-1}$ term in $q$ and covering all nodes’ reverse vertex
edges $E_{3}$ (since the path is Hamiltonian). The reverse path also covers
the $E_{4}$ edges corresponding to reverse Hamiltonian path edges. Our
Eulerian trail is now “at” node $v_{1}^{in}$.

What remains is to complete the Eulerian walk covering (a) edges and their
antiparallel counterparts corresponding to edges in $G$ that were not used in
the Hamiltonian path, and (b) the edges adjacent to node $w$. To do this,
define $\text{pred}(v)$ be the vertices $u$ in $G$ for which edge $(u,v)$
exists and $u$ is not the predecessor of $v$ along the Hamiltonian path. For
each $u\in\text{pred}(v_{1})$, traverse the split edge labeled c# to $u^{out}$
then traverse the forward split edge labeled b# back to $v_{1}^{in}$. This
results in a string $(\texttt{c\\#b\\#})^{|\text{pred}(v_{1})|}$. Once the
predecessors of $v_{1}$ are exhausted, traverse the split edge labeled c# from
$v_{1}^{in}$ into node $w$ and then traverse the split edge labeled b# to
$v_{2}^{in}$. This again generates a c#b# string. Repeat the process, covering
the edges of $v_{2}$’s predecessors and returning to $w$ to move to the next
node along the Hamiltonian path for each node $v_{3},\dots,v_{n}$. After
covering the predecessors of $v_{n}^{in}$, go to $v_{1}^{in}$ through the
remaining edges in $E_{5}$ and $E_{6}$, $(v_{n}^{in},w)$ and $(w,v_{1}^{in})$,
which completes the Eulerian tour. This covers all the edges of
$G^{\prime\prime}$. The word spelled out in this last section of the Eulerian
trail is a sequence of repetitions of c#b#, with one repetition for each edge
that is not in the Hamiltonian path ($|E|-n+1$) and all of the edges in
$E_{5}$ and $E_{6}$ for entering and leaving each node ($2n$), with a total of
$|E|+1$ repetitions, which is the final $(\texttt{c\\#b\\#})^{|E|+1}$ term in
$q$.

This ends the slight modification of the proof in Kupferman and Vardi [7],
where the differences are (a) the introduction of the # characters and (b)
using the exponent $|E|+1$ of the final part of $q$ instead of $|E|+n+1$ as in
Kupferman and Vardi [7] since we create $w$-edges only to $v^{in}$ vertices.
(This second change has no material effect on the proof, but reduces the
length of the string that must be matched.)

Now, given an instance $\langle G=(V,E)\rangle$ of Hamiltonian Path, with
$n=|V|$ vertices, we construct $G^{\prime\prime}$ as above (obtaining a
unidirectional Eulerian graph) and create graph $C$ that only represents
string $q$. Note that $|\Sigma|=4$ and $G^{\prime\prime}$ and $C$ can be
constructed in polynomial time. $\textsc{GTED}(G^{\prime\prime},C)=0$ if and
only if an Eulerian path in $G^{\prime\prime}$ spells out $q$, since there can
be no indels or mismatches. By the above argument, an An eulerian tour that
spells out $q$ exists if and only if $G$ has a Hamiltonian path. ∎

###  A.3 FGTED is NP-complete

######  Problem 4 (Flow Graph Traversal Edit Distance (FGTED) [13]).

Given unidirectional, edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$, each
of which has distinguished $s_{1},s_{2}$ source and $t_{1},t_{2}$ sink
vertices, compute

$\textsc{FGTED}(G_{1},G_{2})\triangleq\min_{\begin{subarray}{c}D_{1}\in\text{flow}(G_{1},s_{1},t_{1})\\\
D_{1}\in\text{flow}(G_{2},s_{2},t_{2})\end{subarray}}\text{emedit}(\textrm{strset}(D_{1}),\textrm{strset}(D_{2})),$
(39)

where $\text{flow}(G_{i},s_{i},t_{i})$ is the collection of all possible sets
of $s_{1}$-$t_{1}$ trail decomposition of saturating flow from $s_{i}$ to
$t_{i}$, $\textrm{strset}(D)$ is the multi-set of strings constructed from
trails in $D$.

######  Theorem 3.

FGTED is NP-complete.

###### Proof.

Let $G=(v,E)$ be an instance of the Hamiltonian Cycle problem. Let $n=|V|$ be
the number of vertices in $G$. Construct the Eulerian closure of $G$ and split
the anti-parallel edges. Let the new graph be
$G^{\prime}=(V^{\prime},E^{\prime})$. Attach a source $s$ and a sink node $t$
to an arbitrary node $v_{1}^{in}$ by adding edge $(s,v_{1}^{in})$ and
$(v_{1}^{in},t)$ with labels s and t, respectively.

Construct a string $q$, such that

$\displaystyle
q=\texttt{sa\\#}(\texttt{b\\#a\\#})^{n-1}(\texttt{c\\#})^{2n-1}(\texttt{c\\#b\\#})^{|E|+1}\texttt{t}.$
(40)

Create a graph $Q$ that only contains one path with labels on the edges of the
path that spell the string $q$. The union of the set of trails in any flow
decomposition of $G^{\prime}$ is equal to a set of Eulerian trails,
$\mathcal{E}$, that starts at $s$ and ends at $t$. All Eulerian trails in
$\mathcal{E}$ are also closed Eulerian trails of
$G^{\prime}\setminus\\{s,t\\}$ that starts and ends at $v_{1}^{in}$.

Using the same line of argument in the proof of Theorem 2, an Eulerian trail
in $G^{\prime}$ that spells $q$ is equivalent to a Hamilton Cycle in $G$. In
addition, $\textsc{FGTED}(Q,G^{\prime})=0$ if and only if all Eulerian trails
in $\mathcal{E}$ spell out $q$. Therefore, if
$\textsc{FGTED}(Q,G^{\prime})=0$, then there is a Hamiltonian Cycle in $G$.
Otherwise, then there must not exist a Hamiltonian Cycle in $G$. ∎

##  Appendix B Equivalence between two ILPs proposed by Ebrahimpour Boroojeny
et al.

The analysis provided by Ebrahimpour Boroojeny et al. [1] states that the LP
relaxation of the ILP in (5)-(8) does not always yield integer solutions, but
the LP relaxation of the ILP in (11)-(12) always yields integer solutions.
This suggests that the two LP relaxations have difference feasibility regions
for $x$. We show that these two LP relaxations are actually equivalent in
Theorem 7. Further, we show that the ILP in (5)-(8) and the ILP in (11)-(12)
are also equivalent. Since the ILP in (5)-(8) does not solve for
$\textsc{GTED}(G_{1},G_{2})$ as shown in 3.2, we conclude that the ILP in
(11)-(12) also does not solve $\textsc{GTED}(G_{1},G_{2})$.

######  Theorem 7.

Given two unidirectional, edge-labeled Eulerian graphs $G_{1}$, $G_{2}$, the
feasibility region of $x$ in the LP relaxation of the ILP in (11)-(12) is the
same as the feasibility region of $x$ in the LP relaxation of the ILP in
(5)-(8).

Let $\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$ be the alignment graph of
$G_{1}=(V_{1},E_{1},\ell_{1},\Sigma_{1})$ and
$G_{2}=(V_{2},E_{2},\ell_{2},\Sigma_{2})$, and let $T(G_{1},G_{2})$ be its
two-simplex set. First, we have the following result:

######  Lemma 4.

Let $[y_{i}]\in\mathbb{R}^{|T(G_{1},G_{2})|}$ be a vector such that the $j$-th
entry of $[y_{i}]$, $[y_{i}]_{j}$ is equal to $0$ for all $j\neq i$. The
vector $x^{\prime}=x+[\partial][y_{i}]$ satisfies the constraints (6)-(7) if
the vector $x$ satisfies the constraints (6)-(7).

###### Proof.

Let $\sigma_{i}\in T(G_{1},G_{2})$ be the 2-simplex corresponding to the entry
$i$ of $[y_{i}]$. Based on the construction of $T(G_{1},G_{2})$, $\sigma_{i}$
has two forms: $[(u_{1},u_{2}),(v_{1},u_{2}),(v_{1},v_{2})]$ or
$[(u_{1},u_{2}),(u_{1},v_{2}),(v_{1},v_{2})]$. Without loss of generality, we
assume $\sigma_{i}=[(u_{1},u_{2}),(v_{1},u_{2}),(v_{1},v_{2})]$. We can prove
this lemma by using the same way when
$\sigma_{i}=[(u_{1},u_{2}),(u_{1},v_{2}),(v_{1},v_{2})]$. Since

$\displaystyle\partial\sigma_{i}=[(u_{1},u_{2}),(v_{1},u_{2})]+[(v_{1},u_{2}),(v_{1},v_{2})]-[(u_{1},u_{2}),(v_{1},v_{2})],$

We have

$\displaystyle[\partial][y_{i}]=[y_{i}]_{i}[x_{e_{1}}]+[y_{i}]_{i}[x_{e_{2}}]-[y_{i}]_{i}[x_{e_{3}}],$

where $e_{1}=[(u_{1},u_{2}),(v_{1},u_{2})]$,
$e_{2}=[(v_{1},u_{2}),(v_{1},v_{2})]$, $e_{3}=[(u_{1},u_{2}),(v_{1},v_{2})]$,
and $[x_{e}]\in\mathbb{R}^{|E|}$ is a vector such that all the entries are $0$
except that the one corresponding to edge $e$ is $1$. we also let
$[x_{v}]\in\mathbb{R}^{|V|}$ be a vector such that all the entries are $0$
except that the one corresponding to vertex $v$ is $1$. Therefore, we have

$\displaystyle
Ax^{\prime}=Ax+[y_{i}]_{i}[x_{v_{2}}]-[y_{i}]_{i}[x_{v_{1}}]+[y_{i}]_{i}[x_{v_{3}}]-[y_{i}]_{i}[x_{v_{2}}]-[y_{i}]_{i}[x_{v_{3}}]+[y_{i}]_{i}[x_{v_{1}}]=Ax,$

where $v_{1}=(u_{1},u_{2})$, $v_{2}=(v_{1},u_{2})$, and $v_{3}=(v_{1},v_{2})$.
Hence, $x^{\prime}$ satisfies the constraint (6) if $x$ satisfies the
constraint (6).

In addition, since $\sum_{e\in E}x_{e}^{\prime}I_{i}(e,f)=\sum_{e\in
E}x_{e}I_{i}(e,f)+[y_{i}]_{i}I_{i}(e_{1},f)+[y_{i}]_{i}I_{i}(e_{2},f)-[y_{i}]_{i}I_{i}(e_{3},f)$,
and:

  * •

$I_{1}(e_{1},(u_{1},v_{1}))=1$ and $I_{i}(e_{1},f)=0$ for other $f\in G_{i}$,

  * •

$I_{2}(e_{2},(u_{2},v_{2}))=1$ and $I_{i}(e_{2},f)=0$ for other $f\in G_{i}$,

  * •

$I_{1}(e_{3},(u_{1},v_{1}))=1$, $I_{2}(e_{3},(u_{2},v_{2}))=1$, and
$I_{i}(e_{3},f)=0$ for other $f\in G_{i}$,

we have:

  * •

$[y_{i}]_{i}I_{1}(e_{1},(u_{1},v_{1}))+[y_{i}]_{i}I_{1}(e_{2},(u_{1},v_{1}))-[y_{i}]_{i}I_{1}(e_{3},(u_{1},v_{1}))=[y_{i}]_{i}+0-[y_{i}]_{i}=0$,

  * •

$[y_{i}]_{i}I_{2}(e_{1},(u_{2},v_{2}))+[y_{i}]_{i}I_{2}(e_{2},(u_{2},v_{2}))-[y_{i}]_{i}I_{2}(e_{3},(u_{2},v_{2}))=0+[y_{i}]_{i}-[y_{i}]_{i}=0$,

  * •

$[y_{i}]_{i}I_{i}(e_{1},f)+[y_{i}]_{i}I_{i}(e_{2},f)-[y_{i}]_{i}I_{i}(e_{3},f)=0+0-0=0$
for any other $i=1,2$ and $f\in E_{i}$.

Therefore, $\sum_{e\in E}x_{e}^{\prime}I_{i}(e,f)=\sum_{e\in
E}x_{e}I_{i}(e,f)$, meaning that $x^{\prime}$ satisfies the constraint (7) if
$x$ satisfies the constraint (7). ∎

With Lemma 4, we prove that any feasible solution of $x$ in (11) is a feasible
solution of (5)-(8). First, it is easy to check that $x^{init}$ satisfies the
constraints (6)-(7). For each feasible solution of $x$ in (11), since
$x=x^{init}+[\partial]y=x^{init}+\sum_{i}[\partial][y_{i}]$, by iteratively
using Lemma 4, we get that $x$ satisfies the constraints (6)-(7). Since
$x_{e}\geq 0$ for all $e\in E$ is a constraint existing in both linear
relaxations, $x$ is a feasible solution of (5)-(8).

We now show that any feasible solution of (5)-(8) is a feasible solution of
(11). Let $x$ be a feasible solution of (5)-(8). We show that $x$ is also a
feasible solution of (11) by proving that $x$ can be converted to $x^{init}$
in (11) via the boundary operator $\partial$. First, if there is a diagonal
edge $e=[(u_{1},u_{2}),(v_{1},v_{2})]$ in $E$ such that $x_{e}>0$, then it can
be replaced by the horizontal edge $e_{h}=[(u_{1},u_{2}),(u_{1},v_{2})]$
followed by the vertical edge $e_{v}=[(u_{1},v_{2}),(v_{1},v_{2})]$ by using
one boundary operation on the 2-simplex
$[(u_{1},u_{2}),(u_{1},v_{2}),(v_{1},v_{2})]$. Hence, $x$ can be converted to
a new vector $x^{\prime}$, such that $x^{\prime}_{e}=0$,
$x^{\prime}_{e_{h}}=x_{e_{h}}+x_{e}$, $x^{\prime}_{e_{v}}=x_{e_{v}}+x_{e}$,
and all the other entries in $x^{\prime}$ are the same as those in $x$. It is
easy to check that $x^{\prime}$ is also a feasible solution of (5)-(8).
Therefore, without loss of generality, we assume $x$ to be a vector such that
all the entries corresponding to diagonal edges in $\mathcal{A}(G_{1},G_{2})$
are zero.

We then prove that any $x$ can be converted to $x^{init}$ in (11) via the
boundary operator. Let the source and the sink node of $x$ in
$\mathcal{A}(G_{1},G_{2})$ be $(s_{1}^{1},s_{1}^{2})$ and
$(s_{2}^{1},s_{2}^{2})$, where $s_{1}^{i}$ is the source node of $G_{i}$ and
$s_{2}^{i}$ is the sink node of $G_{i}$. When the Eulerian trail is closed
(meaning that it is an Eulerian tour) in $G_{i}$, we let $s_{1}^{i}=s_{2}^{i}$
be an arbitrary vertex in $V_{i}$. $x^{init}$ can be seen as a trail (tour) in
$\mathcal{A}(G_{1},G_{2})$ that starts from $(s_{1}^{1},s_{1}^{2})$, walks
along an Eulerian trail of $G_{2}$ via all the horizontal edges $P_{h}$,

$P_{h}=\\{[(s_{1}^{1},s_{1}^{2}),(s_{1}^{1},v_{1}^{2})],[(s_{1}^{1},v_{1}^{2}),(s_{1}^{1},v_{2}^{2})],\dots,[(s_{1}^{1},v_{i-1}^{2}),(s_{1}^{1},v_{i}^{2})],[(s_{1}^{1},v_{i}^{2}),(s_{1}^{1},s_{2}^{2})]\\},$

and then walks along an Eulerian trail of $G_{1}$ via all the vertical edges
$P_{v}$,

$P_{v}=\\{[(s_{1}^{1},s_{2}^{2}),(v_{1}^{1},s_{2}^{2})],[(v_{1}^{1},s_{2}^{2}),(v_{2}^{1},s_{2}^{2})],\dots,[(v_{j-1}^{1},s_{2}^{2}),(v_{j}^{1},s_{2}^{2})],[(v_{j}^{1},s_{2}^{2}),(s_{2}^{1},s_{2}^{2})]\\},$

until the sink node $(s_{2}^{1},s_{2}^{2})$. Here
$\\{s_{1}^{2},v_{1}^{2},v_{2}^{2},\dots,v_{i-1}^{2},v_{i}^{2},s_{2}^{2}\\}$ is
an Eulerian trail of $G_{2}$ and
$\\{s_{1}^{1},v_{1}^{1},v_{2}^{1},\dots,v_{i-1}^{1},v_{i}^{1},s_{2}^{1}\\}$ is
an Eulerian trail of $G_{1}$. We use $P_{0}=\\{P_{h},P_{v}\\}$ to denote the
trail from $(s_{1}^{1},s_{1}^{2})$ to $(s_{2}^{1},s_{2}^{2})$ that is the
concatenation of $P_{h}$ and $P_{v}$. It is easy to see that each edge in
$P_{0}$ is unique.

As shown in Qiu and Kingsford [13], $x$ is a flow of
$\mathcal{A}(G_{1},G_{2})$ with the additional constraint (7). Therefore,
according to the flow decomposition theorem [24, p. 80], $x$ can be decomposed
into a finite set of weighted paths in $\mathcal{A}(G_{1},G_{2})$ from
$(s_{1}^{1},s_{1}^{2})$ to $(s_{2}^{1},s_{2}^{2})$, which is denoted as
$\\{(p_{1},w_{1}^{p}),\dots,(p_{n},w_{n}^{p})\\}$, and a finite set of weight
cycles in $\mathcal{A}(G_{1},G_{2})$, which is denoted as
$\\{(c_{1},w_{1}^{c}),\dots,(c_{m},w_{m}^{c})\\}$. Each path or cycle only
contains horizontal and vertical edges.

For path $i$, we use a vector $x^{p,i}$ to represent $(p_{i},w_{i}^{p})$,

$\displaystyle
x^{p,i}_{e}=\begin{cases}w_{i}^{p}\quad&\text{if}\leavevmode\nobreak\ e\in
p_{i}\\\ 0\quad&\text{otherwise},\end{cases}$ (41)

Figure 7: (a) An example of converting three vertical edges followed by one
horizontal edge (blue line) to one horizontal edge followed by three vertical
edges (red line). It can be done by doing boundary operations on 2-simplices
labeled from $0$ to $5$. (b) An example of a cycle path (red line) and its
auxiliary trail (blue line).

By using the boundary operator, each path $p_{i}$ can actually be converted to
a new trail $p_{i}^{\prime}$ such that each edge in $p_{i}^{\prime}$ is also
an edge in $P_{0}$. To prove this, we consider the following two cases:

  * •

If $p_{i}$ walks along all the horizontal edges followed by all the vertical
edges, then every edge in $p_{i}$ is an edge in $P_{0}$. To see that, let $e$
be an horizontal edge in $p_{i}$, since $p_{i}$ starts from
$(s_{1}^{1},s_{1}^{2})$, $e$ has the form
$[(s_{1}^{1},v),(s_{1}^{1},v^{\prime})]$ where $[v,v^{\prime}]\in E_{2}$.
Since $P_{h}$ corresponds to the Eulerian trail of $G_{2}$, for each
$[v,v^{\prime}]\in E_{2}$, we have $[(s_{1}^{1},v),(s_{1}^{1},v^{\prime})]\in
P_{h}$. Therefore $e\in P_{0}$. We can use the same way to prove $e\in P_{0}$
when $e$ is a vertical edge. Note that in this case, the number of horizontal
edges or vertical edges can be zero.

  * •

If not, then we let $p_{i}=\\{e^{i}_{1},e^{i}_{2},\dots,e^{i}_{m}\\}$, and let
$e^{i}_{t}$ be the vertical edge with the smallest index $t$. There exists an
integer $k\leavevmode\nobreak\ (k\geq 1)$ such that
$\\{e^{i}_{t},e^{i}_{t+1},\dots,e^{i}_{t+k-1}\\}$ are all vertical edges and
$e^{i}_{t+k}$ is an horizontal edge. We denote each vertical edge
$e_{t+w}^{i}\in\\{e^{i}_{t},e^{i}_{t+1},\dots,e^{i}_{t+k-1}\\}$ as
$[(v_{w},v_{t}),(v_{w+1},v_{t})]$ and denote $e^{i}_{t+k}$ as
$[(v_{k},v_{t}),(v_{k},v_{t+1})]$. It is easy to see that when $w=0$,
$v_{w}=s_{1}^{1}$. By using the boundary operator, this subpath
$\\{e^{i}_{t},e^{i}_{t+1},\dots,e^{i}_{t+k-1},e^{i}_{t+k}\\}$ can be replaced
by another subpath with one horizontal edge
$[(s_{1}^{1},v_{t}),(s_{1}^{1},v_{t+1})]$ followed by $k$ vertical edges:

$\\{[(s_{1}^{1},v_{t+1}),(v_{1},v_{t+1})],[(v_{1},v_{t+1}),(v_{2},v_{t+1})],\dots,[(v_{k-1},v_{t+1}),(v_{k},v_{t+1})].$

Now we have a new path, denoted as $p_{i}^{1}$, in which the smallest index of
the vertical edges becomes $t+1$. Figure 7(a) shows an example, in which the
blue line represents the subpath of $p_{i}$ and the red line represents the
new subpath in $p_{i}^{1}$.

To create a new vector that represents $p_{i}^{1}$, we first create a zero
vector $y^{p,i,1}\in\mathbb{R}^{|T(G_{1},G_{2})|}$, and from $w=0$ to $w=k-1$,
we iteratively update $y^{p,i,1}$ via the following equations:

$\displaystyle
y^{p,i,1}_{\sigma}=\begin{cases}y^{p,i,1}_{\sigma}-w_{i}^{p}\quad&\text{if}\leavevmode\nobreak\
\sigma=[(v_{w},v_{t}),(v_{w+1},v_{t}),(v_{w+1},v_{t+1})]\\\
y^{p,i,1}_{\sigma}+w_{i}^{p}\quad&\text{if}\leavevmode\nobreak\
\sigma=[(v_{w},v_{t}),(v_{w},v_{t+1}),(v_{w+1},v_{t+1})]\\\
0\quad&\text{otherwise}.\end{cases}$ (42)

The vector $x^{p,i,1}=x^{p,i}+[\partial]y^{p,i,1}$ is the one that represents
$p_{i}^{1}$.

Since the length of $p_{i}$ is finite, by doing such a transformation a finite
number of times, we can convert $p_{i}$ to a new path $p_{i}^{\prime}$ such
that $p_{i}^{\prime}$ walks along all the horizontal edges first followed by
all the vertical edges, therefore each edge in $p_{i}^{\prime}$ is also an
edge in $P_{0}$. We use the vector $\hat{x}^{p,i}$ to represent
$p_{i}^{\prime}$, $\hat{x}^{p,i}=x^{p,i}+[\partial]\sum_{j=1}^{q}y^{p,i,j}$
where $q$ is the number of transformations. Apperantly, $\hat{x}^{p,i}_{e}=0$
when $e\notin P_{0}$. Let $y^{p,i}=\sum_{j=1}^{q}y^{p,i,j}$, we have
$\hat{x}^{p,i}=x^{p,i}+[\partial]y^{p,i}$.

For cycle $i$, we also use a vector $x^{c,i}$ to represent
$(c_{i},w_{i}^{c})$,

$\displaystyle
x^{c,i}_{e}=\begin{cases}w_{i}^{c}\quad&\text{if}\leavevmode\nobreak\ e\in
c_{i}\\\ 0\quad&\text{otherwise},\end{cases}$ (43)

Let $(v,v^{\prime})$ be an arbitrary chosen node in $c_{i}$, we construct a
trail $p_{aux}^{i}$ that passes $(v,v^{\prime})$ as follows:

  * •

From $(s_{1}^{1},s_{1}^{2})$, walk along $P_{h}$ until the node
$(s_{1}^{1},v^{\prime})$. It corresponds to a part of an Eulerian trail of
$G_{2}$.

  * •

From $(s_{1}^{1},v^{\prime})$, walk along an Eulerian trail of $G_{1}$ to
$(s_{2}^{1},v^{\prime})$. It must passes the node $(v,v^{\prime})$.

  * •

From $(s_{2}^{1},v^{\prime})$, walk along the remaining part of the Eulerian
trail of $G_{2}$ to the node $(s_{2}^{1},s_{2}^{2})$.

Figure 7(b) shows an example, in which the blue line represents $p_{aux}^{i}$
and the red line represents $c_{i}$.

We use $x^{aux,i}$ to denote the vector representing $p_{aux}^{i}$. The
combination of $c_{i}$ and $p_{aux}^{i}$, represented by the vector
$x^{c,i}+x^{aux,i}$ creates a new trail (may have repeated edges) from
$(s_{1}^{1},s_{1}^{2})$ to $(s_{2}^{1},s_{2}^{2})$: (1) walk along
$p_{aux}^{i}$ from $(s_{1}^{1},s_{1}^{2})$ to $(v,v^{\prime})$, (2) walk along
$c_{i}$ from $(v,v^{\prime})$ to itself, and (3) walk along the remaining part
of $p_{aux}^{i}$ from $(v,v^{\prime})$ to $(s_{2}^{1},s_{2}^{2})$. By using
the same way as we described above, each $c_{i}+p_{aux}^{i}$ or $p_{aux}^{i}$
can be converted to a new trail in which each edge is also an edge in $P_{0}$.
We use $\hat{x}^{c,i}$ or $\hat{x}^{aux,i}$ to represent the new trail
accordingly, therefore, we have
$\hat{x}^{c,i}=x^{c,i}+x^{aux,i}+[\partial]y^{c,i}$ and
$\hat{x}^{aux,i}=x^{aux,i}+[\partial]y^{aux,i}$. Likewise,
$\hat{x}^{c,i}_{e}=\hat{x}^{aux,i}_{e}=0$ when $e\notin P_{0}$.

We define a new vector $\hat{x}$ such that:

$\displaystyle\hat{x}$
$\displaystyle=\sum_{i=1}^{n}\hat{x}^{p,i}+\sum_{j=1}^{m}\hat{x}^{c,j}-\hat{x}^{aux,j}$
$\displaystyle=\sum_{i=1}^{n}x^{p,i}+[\partial]y^{p,i}+\sum_{j=1}^{m}x^{c,j}+x^{aux,j}+[\partial]y^{c,j}-\left(\sum_{j=1}^{m}x^{aux,j}+[\partial]y^{aux,j}\right)$
$\displaystyle=\sum_{i=1}^{n}x^{p,i}+\sum_{j=1}^{m}x^{c,j}+[\partial]\left(\sum_{i=1}^{n}y^{p,i}+\sum_{j=1}^{m}y^{c,j}-\sum_{j=1}^{m}y^{aux,j}\right)$
$\displaystyle=x+[\partial]\left(\sum_{i=1}^{n}y^{p,i}+\sum_{j=1}^{m}y^{c,j}-\sum_{j=1}^{m}y^{aux,j}\right).$

Therefore, $\hat{x}$ is a vector converted from $x$ via boundary operations.
$\hat{x}$ is equal to $x^{init}$ because:

  1. 1.

$\hat{x}_{e}=0$ when $e\notin P_{0}$ since
$\hat{x}^{p,i}_{e}=\hat{x}^{c,i}_{e}=\hat{x}^{aux,i}_{e}=0$ when $e\notin
P_{0}$ for each $i$.

  2. 2.

As we have proved above, the boundary operator preserves the constraints
(6)-(7). Therefore, $\hat{x}$ satisfies the constraints (6)-(7) since $x$ is a
feasible solution of (5)-(8). Combined with the first point, we have that
$\hat{x}_{e}=1$ if $e\in P_{0}$ and $\hat{x}_{e}=0$ otherwise, meaning that
$\hat{x}=x^{init}$.

Hence, for each feasible solution $x$ of (5)-(8), we have:

$\displaystyle x$
$\displaystyle=x^{init}-[\partial]\left(\sum_{i=1}^{n}y^{p,i}+\sum_{j=1}^{m}y^{c,j}-\sum_{j=1}^{m}y^{aux,j}\right)$
$\displaystyle=x^{init}+[\partial]\left(-\sum_{i=1}^{n}y^{p,i}-\sum_{j=1}^{m}y^{c,j}+\sum_{j=1}^{m}y^{aux,j}\right),$

meaning that $x$ is also a feasible solution of (11).

We proved that the feasibility region of $x$ in (11) is the same as the
feasibility region of $x$ in (5)-(8), and since the objective functions of
these two linear relaxations are the same, the optimal solutions of them are
equal.

By employing the same approach and taking into account that if all edge
weights in a flow network are non-negative integers, the flow decomposition
theorem guarantees that the network can be decomposed into a finite set of
weighted paths and cycles, each with positive integer weight, we can prove
that the ILP in (5)-(8) and the ILP in (11)-(12) are also equivalent.

Based on the proof, we can conclude that the way to index the vertices or
edges in the alignment graph, or the 2-simplices in $T(G_{1},G_{2})$, will not
affect the equivalence result. Additionally, different choices of orientations
for the 2-simplices in $T(G_{1},G_{2})$ will also not impact the equivalence
result. This is because for any two sets $T(G_{1},G_{2})$ and
$T^{\prime}(G_{1},G_{2})$ containing the same 2-simplices with the same
indices but different orientations, if $(x,y)$ is a feasible solution of the
ILP in (11)-(12) (or its relaxation) that corresponds to $T(G_{1},G_{2})$,
then $(x,y^{\prime})$ is a feasible solution of the ILP in (11)-(12) (or its
relaxation) that corresponds to $T^{\prime}(G_{1},G_{2})$, where
$y_{i}=y^{\prime}_{i}$ when $\sigma_{i}\in T(G_{1},G_{2})$ has the same
orientation as $\sigma^{\prime}_{i}\in T^{\prime}(G_{1},G_{2})$, and
$y_{i}=-y^{\prime}_{i}$ when $\sigma_{i}\in T(G_{1},G_{2})$ has the opposite
orientation to $\sigma^{\prime}_{i}\in T^{\prime}(G_{1},G_{2})$. Therefore, it
is acceptable to specify a particular orientation for each 2-simplex when
defining $T(G_{1},G_{2})$.

##  Appendix C The linear relaxation of the ILP in (11)-(12) does not always
yield integer solutions

###  C.1 $[\partial]$ is not necessarily totally unimodular

Figure 8: (a) Subgraphs $G_{1}^{sub}$ and $G_{2}^{sub}$ of input graphs
$G_{1}$ and $G_{2}$. Dots represent a path from node 1 to $k-1$ with middle
nodes omitted. (b) The alignment graph $\mathcal{A}(G_{1}^{sub},G_{2}^{sub})$
with different edges labeled with colors. (c) A subgraph of the alignment
graph in (b) with edges and triangles numbered. Dots represent horizontal and
diagonal edges omitted. The same vertices that are repeated in (c) are marked
with yellow and red filling colors.

A linear programming formulation always yields integer solutions if its
constraint matrix is totally unimodular, which means that all of its square
submatrices have determinants of 0, -1 or 1 [25]. To show that the constraint
matrix of the LP relaxation of the ILP in (11)-(12) is not totally unimodular,
we first write the LP in standard form.

In a standard form of a LP, all variables are greater than, or equal to 0.
Since $y$ vectors in the LP relaxation of the ILP in (11)-(12) can contain
negative entries, we decompose it into $y^{+}-y^{-}$. Given alignment graph
$\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$ and $T(G_{1},G_{2})$, we can now write
the standard form of the LP in (11)-(12) as

$\displaystyle\underset{x\in\mathbb{R}^{|E|},y^{+},y^{-}\in\mathbb{R}^{|T(G_{1},G_{2})|}}{\textrm{minimize}}$
$\displaystyle\sum_{e\in E}x_{e}\delta(e)$ (44) subject to
$\displaystyle\quad\left[I,-[\partial],[\partial]\right][x,y^{+},y^{-}]^{\top}=x^{init}$
$\displaystyle\quad x,y^{+},y^{-}\geq 0.$

Hence the constraint matrix of the LP relaxation is
$A=\left[I,-[\partial],[\partial]\right]$. According to the characteristics of
a totally unimodular matrix [26, p. 280] $A$ is not totally unimodular if
$[\partial]$ is not totally unimodular. We show that $[\partial]$ is not TU
when the input graphs satisfy the constraints given in the following theorem.

######  Theorem 8.

Given two unidirectional, edge-labeled Eulerian graphs $G_{1}$ and $G_{2}$
where $|E_{1}|\geq 2$ and $|E_{2}|\geq 2$, the boundary matrix $[\partial]$
constructed from $\mathcal{A}(G_{1},G_{2})=(V,E,\delta)$ and $T(G_{1},G_{2})$
is not totally unimodular if there is a vertex $v\in
V_{1}\text{\leavevmode\nobreak\ or\leavevmode\nobreak\ }V_{2}$ such that there
are at least 3 unique edges in $E_{1}$ or $E_{2}$ that are incident to $v$.
Here, unique edges are edges that connect to $v$ at one end but have different
endpoints at the other end.

###### Proof.

To prove that the boundary matrix is not TU, we only need to show that it is
not TU under one specific chosen orientation for 1- and 2-simplices, as well
as one specific chosen set of indices for 1- and 2-simplices. This is because
changing the orientations or indices of 1-simplices in $E$ or 2-simplices in
$T(G_{1},G_{2})$ corresponds to permuting rows and columns of $[\partial]$ or
multiplying rows and columns of $[\partial]$ by $-1$, which preserves the
total unimodularity [26, p. 280].

Without loss of generality, let $v_{0}\in V_{1}$ be a node that is incident to
at least 3 unique edges. Since $G_{1}$ is an Eulerian graph, $v$ must be part
of a cycle $C$ in $G_{1}$. Also, there must exist another node $v_{k}$ and an
edge between $v_{0}$ and $v_{k}$ in either direction, such that the edge
between $v_{0}$ and $v_{k}$ is not contained in cycle $C$ (Figure 8(a)).
Suppose the number of nodes in the cycle is $k$ ($k\geq 3$ due to the
unidirectionality constraint), and let the cycle
$C=v_{0},v_{1},\dots,v_{k-1}$. Since a specific choice of 1-simplex
orientations does not affect the total unimodularity of the boundary matrix,
we assume the edge between $v_{0}$ and $v_{k}$ is $[v_{k},v_{0}]$ without loss
of generality. We use $G_{1}^{sub}=(V_{1}^{sub},E_{1}^{sub})$ to denote the
subgraph with $V_{1}^{sub}=\\{v_{0},\dots,v_{k-1},v_{k}\\}$ and
$E_{1}^{sub}=\left\\{[v_{i},v_{i+1}]:i\in\\{0,1,\dots
k-2\\}\right\\}\cup\\{[v_{k},v_{0}]\\}$. Since $|E_{2}|\geq 2$ and $G_{2}$ is
a connected graph, there exist two consecutive, directed edges in $G_{2}$. We
use $G_{2}^{sub}=(V_{2}^{sub},E_{2}^{sub})$ to denote the subgraph of $G_{2}$
with $V_{2}^{sub}=\\{v_{a},v_{b},v_{c}\\}$ and
$E_{2}^{sub}=\\{[v_{a},v_{b}],[v_{b},v_{c}]\\}$. The alignment graph
$\mathcal{A}(G_{1}^{sub},G_{2}^{sub})$ is formed with $G_{1}^{sub}$ and
$G_{2}^{sub}$ and is a subgraph of $\mathcal{A}(G_{1},G_{2})$, therefore, each
subgraph of $\mathcal{A}(G_{1}^{sub},G_{2}^{sub})$ is also a subgraph of
$\mathcal{A}(G_{1},G_{2})$. Similarly, the 2-simplex set
$T(G_{1}^{sub},G_{2}^{sub})$ is a subset of $T(G_{1},G_{2})$.

We extract a sequence of 2-simplices (Figure 8(c)), $T_{c}$, from
$T(G_{1}^{sub},G_{2}^{sub})$ via following steps:

  1. 1.

Extract all oriented 2-simplices
$[(v_{i},v_{a}),(v_{i},v_{b}),(v_{i+1},v_{b})]$ and
$[(v_{i},v_{a}),(v_{i+1},v_{a}),(v_{i+1},v_{b})]$ for $0\leq i\leq k-2$ from
$T(G_{1}^{sub},G_{2}^{sub})$.
Flip the orientations of $[(v_{i},v_{a}),(v_{i+1},v_{a}),(v_{i+1},v_{b})]$ for
all $0\leq i\leq k-2$, obtaining
$[(v_{i},v_{a}),(v_{i+1},v_{b}),(v_{i+1},v_{a})]$. Use $\sigma_{2i}$ to denote
$[(v_{i},v_{a}),(v_{i},v_{b}),(v_{i+1},v_{b})]$, and $\sigma_{2i+1}$ to denote
$[(v_{i},v_{a}),(v_{i+1},v_{b}),(v_{i+1},v_{a})]$.

  2. 2.

Add to the sequence another five oriented 2-simplices from
$T(G_{1}^{sub},G_{2}^{sub})$ in the order as specified:
$\sigma_{2k-2}=[(v_{k-1},v_{a}),(v_{k-1},v_{b}),(v_{0},v_{b})]$,
$\sigma_{2k-1}=[(v_{k-1},v_{b}),(v_{0},v_{b}),(v_{0},v_{c})]$,
$\sigma_{2k}=[(v_{k},v_{b}),(v_{0},v_{b}),(v_{0},v_{c})]$,
$\sigma_{2k+1}=[(v_{k},v_{a}),(v_{k},v_{b}),(v_{0},v_{b})]$ and finally
$\sigma_{2k+2}=[(v_{k},v_{a}),(v_{0},v_{a}),(v_{0},v_{b})]$.

In total, we extract a sequence of $(2k+3)$ oriented 2-simplices,
$T_{c}=\\{\sigma_{0},\sigma_{1},\dots,\sigma_{2k+2}\\}$, such that
$\sigma_{i}$ and $\sigma_{i+1\mod(2k+3)}$ share one edge. The extracted
2-simplices and their orientations as well as all shared edges are shown in
Figure 8(c). We flip the orientations of
$[(v_{i},v_{a}),(v_{i+1},v_{a}),(v_{i+1},v_{b})]$ solely to ensure that the
submatrix constructed below has a simple form, which makes it easier to
compute the determinant.

Based on $T_{c}$, we obtain $M_{1}$, a $(2k+3)\times(2k+3)$ submatrix of
$[\partial]$ where each roll corresponds to a shared edge and each column
corresponds to a 2-simplex in $T_{c}$. The entry values of $M_{1}$ are the
signed coefficients of each selected 1-simplex from the boundaries of selected
2-simplices.

$\displaystyle M_{1}=\begin{bmatrix}1&0&\dots&0&0&0&0&0&0&1\\\
-1&1&\dots&0&0&0&0&0&0&0\\\ 0&-1&\dots&0&0&0&0&0&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\dots&1&0&0&0&0&0&0\\\ 0&0&\dots&-1&1&0&0&0&0&0\\\
0&0&\dots&0&-1&1&0&0&0&0\\\ 0&0&\dots&0&0&1&1&0&0&0\\\
0&0&\dots&0&0&0&1&1&0&0\\\ 0&0&\dots&0&0&0&0&1&1&0\\\
0&0&\dots&0&0&0&0&0&-1&-1\end{bmatrix}$

The determinant of $M_{1}$ is:

$\displaystyle\det M_{1}$
$\displaystyle=\det\begin{bmatrix}-1&1&\dots&0&0&0&0&0&0\\\
0&-1&\dots&0&0&0&0&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\dots&1&0&0&0&0&0\\\ 0&0&\dots&-1&1&0&0&0&0\\\ 0&0&\dots&0&-1&1&0&0&0\\\
0&0&\dots&0&0&1&1&0&0\\\ 0&0&\dots&0&0&0&1&1&0\\\ 0&0&\dots&0&0&0&0&1&1\\\
0&0&\dots&0&0&0&0&0&-1\end{bmatrix}-\det\begin{bmatrix}1&0&\dots&0&0&0&0&0&0\\\
-1&1&\dots&0&0&0&0&0&0\\\ 0&-1&\dots&0&0&0&0&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\dots&1&0&0&0&0&0\\\ 0&0&\dots&-1&1&0&0&0&0\\\ 0&0&\dots&0&-1&1&0&0&0\\\
0&0&\dots&0&0&1&1&0&0\\\ 0&0&\dots&0&0&0&1&1&0\\\
0&0&\dots&0&0&0&0&1&1\end{bmatrix}$
$\displaystyle=(-1)^{2k-2}\times(-1)-1^{2k+2}=-2.$

Since the determinant of $M_{1}$ is -2, and $M_{1}$ is a submatrix of
$[\partial]$, $[\partial]$ is not totally unimodular. ∎

The minimal pair of input graphs that satisfy the conditions in Theorem 8 is a
graph with one 3-node cycle and one additional edge incident to the cycle and
an acyclic, connected graph with three nodes. In practice, most non-trivial
edge-labeled Eulerian graphs satisfy these conditions.

According to the definitions in Dey et al. [25], the subgraph used to
construct $M_{1}$ in the above proof (Figure 8(c)) is a Möbius subcomplex, and
$M_{1}$ is a $(2k+3)$-Möbius cycle matrix (MCM). Theorem 8 also establishes
that there may exist a Möbius subcomplex in an alignment graph, which corrects
the false claim made in Lemma 2 in [1].

Theorem 2 in Ebrahimpour Boroojeny et al. [1] attempts to employ a more
algebraic approach to attempt to demonstrate that $[\partial]$ is TU by
establishing that the alignment graph is a Möbius-free product space. However,
the property of being Möbius-free globally does not imply the absence of
Möbius subcomplexes locally. As we show in Theorem 8, although the alignment
graph $\mathcal{A}(G_{1}^{sub},G_{2}^{sub})$ is homotopically equivalent to
the one-dimensional circle, which is Möbius-free, it still contains a Möbius
subcomplex.

Figure 9: An example of a fractional optimal solution to the LP in (11)-(12)
and the LP in (5)-(8). (a) A pair of input graphs to the LP in (11)-(12) and
the LP in (5)-(8). Letters in red are edge labels. (b) A subgraph of
$\mathcal{A}(G_{1},G_{2})$ that is induced by alignment edges with non-zero
weights (blue font) in an optimal solution to the LPs. The letters in red show
the matching between the edge labels or between edge labels and gaps.

###  C.2 The LP yields optimal fractional solutions

The fact that $[\partial]$ is not totally unimodular does not guarantee that
the LP in (11)-(12) has a fractional optimal objective value. In this section,
we prove that the LP in (11)-(12) does not always yield integer optimal
solutions by constructing a specific example with a fractional optimal
objective value.

######  Theorem 9.

The LP in (5)-(8) and the LP in (11)-(12) do not always yield optimal integer
solutions.

We prove the above theorem by giving an example where the LP in (5)-(8) yields
a fractional optimal solution. Since by Theorem 7, two LPs are equivalent, it
follows that the LP in (11)-(12) also yields the same fractional optimal
solution.

Construct $G_{1}$ and $G_{2}$ such that their edges and edge labels are equal
to the ones specified in Figure 9(a). Let the edge multi-set of
$\mathcal{A}(G_{1},G_{2})$ be $E$. We assign an edge cost to 0 if the edge
matches two equal characters and 1 otherwise. Construct vector
$x^{*}\in\mathrm{R}^{|E|}$ and set entries corresponding to edges in Figure
9(b) to 0.5 except edge $[(v_{3},v_{c}),(v_{0},v_{f})]$ to which the
corresponding entry is set to 1. Set the rest of the entries of $x^{*}$ to 0.

######  Lemma 5.

$x^{*}$ is an optimal solution to the LP in (5)-(8) constructed with
$\mathcal{A}(G_{1},G_{2})$ and $T(G_{1},G_{2})$.

###### Proof.

We prove the optimality of $x^{*}$ via complementary slackness. We first write
the LP in (5)-(8) in standard form.

$\displaystyle\underset{x\in\mathbb{R}^{|E|}}{\textrm{minimize}}$
$\displaystyle\quad\sum_{e\in E}\delta_{e}x_{e}$ (45) subject to
$\displaystyle\quad Ax=b$ $\displaystyle x_{e}\geq 0\quad\textrm{ for all
}e\in E.$

Here, $\delta$ is a vector of size $|E|$ where each entry is cost of edge $e$.
The constraint matrix $A$ of the primal LP (45) has $|E|$ columns and
$|V|+|E_{1}|+|E_{2}|=m$ rows, where $V$ is the vertex set of
$\mathcal{A}(G_{1},G_{2})$, and $E_{1}$ and $E_{2}$ are edge multi-sets of the
input graphs. The first $|V|$ rows correspond to the constraints specified in
(6). The rest of the rows correspond to the constraints in (7) that enforce
the projected multi-set of edges to be equal to the multi-set of edges in each
input graph. Since the input graphs both contain Eulerian tours, the vector
$b$ has size $m$, where the first $|V|$ entries are zeroes and the rest of the
entries are 1s.

We write the dual form of LP (45) as follows.

$\displaystyle\underset{y\in\mathbb{R}^{m}}{\textrm{maximize}}$
$\displaystyle\quad\sum_{j=1}^{m}b_{j}y_{j}$ (46) subject to
$\displaystyle\quad A^{\top}y\leq\delta.$

Let the objective value of LP (45) given a $x$ as input is
$\textrm{obj}^{p}_{x}$, and the objective value of LP (46) given a $y$ as
input is $\textrm{obj}^{d}_{y}$. To show that $x^{*}$ is an optimal solution
to the LP in (5)-(8), we need to show that there exists a feasible solution to
the dual LP, $y^{*}$, that satisfies the complementary slackness conditions
and that $\textrm{obj}^{d}_{y^{*}}=\textrm{obj}^{p}_{x^{*}}$.

Since each alignment edge has two endpoints and is projected to at most one
edge in each graph, there are at most 4 non-zero entries in each column of
$A$. The variables in $y$ of the dual form can be interpreted in three parts.
Each of the first $|V|$ entries of $y$ can be assigned to each vertex in the
alignment graph, and the next $|E_{1}|$ entries can be assigned to edges in
$G_{1}$ and the last $|E_{2}|$ entries can be assigned to edges in $G_{2}$.
There are $|E|$ constraints in the dual LP, and the $e$-th constraint can be
assigned to one edge in the alignment graph has cost $\delta_{e}$. Therefore,
each constraint that is assigned to a horizontal or a vertical edge can be
written as

$y_{v^{out}_{e}}-y_{v^{in}_{e}}+y_{e_{i}}\leq\delta_{e},$ (47)

where $i=1$ if $e$ is a horizontal edge, and $i=2$ if $e$ is a vertical edge.
$y_{v^{in}_{e}}$ and $y_{v^{out}_{e}}$ are the $y$ entries that are assigned
to the vertices that are the start and end of edge $e$, and $y_{e_{i}}$ are
the $y$ entries that assigned to the $\pi_{i}(e)$.

Similarly, each constraint that is assigned to a diagonal edge is

$y_{v^{in}_{e}}-y_{v^{out}_{e}}+y_{e_{1}}+y_{e_{2}}\leq\delta_{e}.$ (48)

We can verify that $x^{*}$ is a feasible solution of the primal form (45) by
checking if constraints (6)-(7) are satisfied. The primal objective value can
be computed in a straightforward way, and we can obtain
$\textrm{obj}^{p}_{x^{*}}=3.5.$

According to complementary slackness conditions, since $x^{*}_{e}>0$ for edges
shown in Figure 9(b), the corresponding constraints in the dual LP (46) must
be tight, meaning that the equality must hold in these constraints. The rest
of the dual constraints could have slacks.

Let the subgraph of $\mathcal{A}(G_{1},G_{2})$ shown in Figure 9(b) be
$A^{\prime}$. Denote the cycle that traverses from $[(0,f),(4,a)]$ to
$[(3,c),(0,f)]$ be $C^{\prime}$ and the 4-node cycle that traverses
$((0,f),(1,a),(2,e),(3,c))$ be $C^{\prime\prime}$. Denote the concatenation of
two cycles with $C$. The projected cycle from $C$ to $G_{1}$ is

$\displaystyle
C_{1}=(v_{0},v_{4},v_{5},v_{0},v_{4},v_{5},v_{0},v_{1},v_{2},v_{3},v_{0},v_{1},v_{2},v_{3},v_{0}).$
(49)

The projected cycle from $C$ to $G_{2}$ is

$\displaystyle
C_{2}=(v_{f},v_{a},v_{e},v_{c},v_{d},v_{a},v_{b},v_{c},v_{d},v_{a},v_{b},v_{c},v_{f},v_{a},v_{e},v_{c},v_{f}).$
(50)

Sum up all the constraints that are assigned edge $e$ where $x^{*}_{e}>0$.
Since these edges form a cycle, we get:

$\displaystyle\sum_{e\in
C}\big{(}y_{v_{e}^{out}}-y_{v_{e}^{in}}\big{)}+2\big{(}\sum_{e_{1}\in
C_{1}}y_{e_{1}}+\sum_{e_{2}\in C_{2}}y_{e_{2}}\big{)}$ (51)
$\displaystyle=\quad$ $\displaystyle 0+2\big{(}\sum_{e_{1}\in
C_{1}}y_{e_{1}}+\sum_{e_{2}\in C_{2}}y_{e_{2}}\big{)}$ (52)
$\displaystyle=\quad$ $\displaystyle\sum_{e\in C}\delta_{e}=7,$ (53)
$\displaystyle\Rightarrow\quad$ $\displaystyle\sum_{e_{1}\in
C_{1}}y_{e_{1}}+\sum_{e_{2}\in C_{2}}y_{e_{2}}=3.5.$ (54)

The summed edge cost is 7 as there are 7 edges that are either mismatch edges
or vertical edges.

All $y$ entries that correspond to vertices are free variables and are in
every constraint. After fixing the $y$ variables that satisfy constraint (54),
the rest of the $y$ variables can be set to satisfy the dual cosntraint. We
now obtain $y^{*}$ which is a feasible solution to the dual LP.

The only entries in $y^{*}$ that could have non-zero dual costs are those that
correspond to edges in $E_{1}$ and $E_{2}$. Since these corresponding dual
costs are all 1,

$\displaystyle\textrm{obj}^{d}_{y^{*}}=\sum_{e_{1}\in
C_{1}}y_{e_{1}}+\sum_{e_{2}\in C_{2}}y_{e_{2}}=3.5=\textrm{obj}^{p}_{x^{*}}.$

∎

Since the costs of alignment graph edges are all integers, the fact that the
LP in (11)-(12) and the LP in (5)-(8) yield fractional optimal objective
values mean that they must yield fractional solutions and assign fractional
values to entries in $x$. Theorem 9 follows. Since the LP in (11)-(12) yields
fractional solutions and GTED is always an integer, solving the LP in
(11)-(12) does not solve GTED.

##  Appendix D The average wall-clock time to solve ILPs on 3-cycle graphs

Table S1: The average wall-clock time to solve (lower bound ILP), (exponential ILP), (compact ILP) and the number of iterations for pairs of 3-cycle graphs for each $\textsc{GTED}-\textsc{GTED}_{l}$. GTED - $\textsc{GTED}_{l}$ |  |  (lower bound ILP)
---
runtime (s)
| GTED iterative
---
runtime (s)
Iterations |  | GTED compact
---
runtime (s)
1.0 | 0.06 | 0.17 | 3.55 | 0.39
2.0 | 0.05 | 0.87 | 13.00 | 0.43
3.0 | 0.08 | 25.41 | 67.60 | 1.24
4.0 | 0.07 | 205.59 | 179.10 | 1.70
5.0 | 0.08 | 943.68 | 502.85 | 5.37