In a study published in Algorithms for Molecular Biology, researchers Yutong Qiu, Yihang Shen, and Carl Kingsford have resolved a fundamental contradiction in theoretical bioinformatics by demonstrating that graph traversal edit distance is NP-complete. First introduced in 2018 by Ebrahimpour Boroojeny and colleagues, graph traversal edit distance was conceived as an elegant metric for comparing edge-labeled Eulerian graphs without performing full genome assembly. The original authors claimed that this distance could be computed in polynomial time through linear programming relaxations of integer linear programs. However, this assertion contradicted established computational complexity results for string-to-graph matching problems. The new investigation settles this longstanding conflict by proving that graph traversal edit distance is NP-complete, demonstrating that previous polynomial-time claims rested on flawed mathematical foundations.
Graph traversal edit distance was developed to address a central challenge in computational genomics: comparing complex sequence graphs directly without undergoing costly genome assembly. In modern sequence analysis, read data are frequently represented as de Bruijn graphs, modeling overlapping sequence fragments as connected directed networks. Formally, the problem evaluates unidirectional, edge-labeled Eulerian graphs, defined as connected directed graphs with a vertex set, an edge multi-set, a constant alphabet, and single-character edge labels where an Eulerian trail visits each edge once. Computing graph traversal edit distance requires finding two Eulerian trails, one from each graph, minimizing the edit distance between strings reconstructed from their edge labels. This formulation previously clustered Hepatitis B viral graphs into taxonomic groupings, highlighting its conceptual appeal for analyzing metagenomic communities and disease samples.
Despite its conceptual appeal, the original claim that graph traversal edit distance could be solved in polynomial time conflicted with core complexity theorems. In their 2018 paper, Ebrahimpour Boroojeny and coauthors proposed two integer linear programming models, asserting that the linear relaxation of one formulation always yielded optimal integer solutions because its constraint matrix was totally unimodular. This result contradicted landmark findings by Orna Kupferman and Moshe Vardi, who proved that deciding whether a string matches an Eulerian tour in an edge-labeled graph is NP-complete. Furthermore, existing research demonstrated that calculating edit distances between strings and graphs is NP-complete whenever edits on graphs are permitted. Under the standard assumption that P does not equal NP, both complexity claims could not simultaneously be true.
To resolve the conflict, Qiu, Shen, and Kingsford established that graph traversal edit distance is NP-complete through a reduction from the Hamiltonian path problem. That classic problem asks whether a directed simple graph without self-loops or parallel edges contains a path visiting every vertex exactly once. The authors constructed an Eulerian closure of an arbitrary graph by splitting each vertex into input and output nodes, adding an auxiliary node, and assigning labeled edges. To satisfy unidirectional graph requirements, anti-parallel edges were replaced by length-two paths with designated label extensions. By creating a second comparison graph that spells a single structured sequence, the authors proved that the Hamiltonian path instance possesses a valid solution if and only if the graph traversal edit distance equals zero.
The authors extended their complexity analysis to Flow-GTED, an important variant designed for comparative pangenomics. Proposed in earlier research by Qiu and Kingsford, Flow-GTED evaluates differences between sets of strings reconstructed from network flows between designated source and sink vertices, measuring similarity through Earth Mover’s Edit Distance. Because earlier work reduced Flow-GTED to graph traversal edit distance and relied on the claimed polynomial solver, Flow-GTED was also thought to be polynomially solvable. The authors demonstrated that Flow-GTED is likewise NP-complete. Additionally, examining the 2018 integer linear program revealed that its constraint matrix is not always totally unimodular. The team identified optimal fractional solutions to its linear relaxation, disproving the earlier theoretical claim and showing that linear relaxations cannot guarantee polynomial-time integer solutions.
Crucially, the research revealed that the original 2018 integer linear programs do not solve graph traversal edit distance. Those formulations rely on an alignment graph constructed from the product of the input graph vertices, featuring vertical, horizontal, and diagonal edges representing deletions, insertions, and matches or mismatches. The 2018 formulation attempted to identify a minimum-cost trail using standard flow conservation and edge projection constraints. However, the authors showed that these constraints permit solutions consisting of multiple disjoint cycles in the alignment graph rather than a single unified Eulerian trail. In an explicit counter-example using graphs spelling circular permutations of six-character sequences, the authors proved that the 2018 model selected disconnected cycles yielding a zero-cost objective, even though the true edit distance was two.
The authors discovered that while the 2018 model fails to compute graph traversal edit distance, it solves an alternative metric they termed closed-trail cover traversal edit distance, or CCTED. This metric represents a valid lower bound on the true distance. Instead of requiring a single Eulerian trail, CCTED seeks edge-disjoint closed-trail covers of both graphs that minimize the matching cost between constituent trails, evaluated through a min-cost item matching framework. While CCTED provides a useful local distance metric for comparing genomes with segmental duplications or structural repeats, it diverges from global traversal distances whenever disconnected cycles occur. Furthermore, by reducing from the Eulerian Trail Equaling Word problem, the authors proved that calculating CCTED is also an NP-complete problem, confirming that local relaxations remain computationally hard.
To provide sound methods for calculating graph traversal edit distance, the researchers developed two new integer linear programming formulations accommodating both open and closed Eulerian trails. Both formulations augment the alignment graph with auxiliary source and sink nodes connected to valid trail endpoints. The first formulation eliminates disconnected cycles using iterative constraint generation adapted from traveling salesman algorithms. The procedure initially solves a relaxed flow model and inspects the resulting subgraph for strongly connected components lacking connection to the sink node. Whenever disconnected components appear, the solver generates linear subtour elimination inequalities that compel the selection of outgoing edges from those components. The algorithm repeats this cycle iteratively until the selected edges strictly form a single continuous trail connecting source and sink.
To avoid the potentially exponential iteration counts of constraint generation, the authors introduced a compact integer linear program featuring a polynomial number of constraints. Inspired by the Miller-Tucker-Zemlin traveling salesman formulation, this model assigns auxiliary ordering variables to every alignment edge. These variables enforce a partial ordering along selected paths, requiring consecutive edges to increment by one. Node-level conservation constraints balance the differences between incoming and outgoing order sums against the number of traversing edges, while source and sink edges anchor boundary conditions. Binary indicator variables ensure that unselected edges have ordering variables set to zero. The authors proved mathematically that these polynomial ordering constraints prevent disconnected cycles, guaranteeing that any feasible integer solution strictly corresponds to a single connected Eulerian trail.
The authors evaluated the efficiency of their formulations through computational experiments on an enterprise Linux server configured with dual Intel Xeon E5-2690 v3 processors running at 2.60 gigahertz, with 48 cores, 96 threads, and 378 gigabytes of memory. Models and linear relaxations were solved using the Gurobi optimization suite executing across 32 parallel threads. The evaluation examined 20 de Bruijn graphs constructed with k-mer length four from 150-character sequence segments extracted from T-cell receptor variable genes in the IMGT database. Across 190 pairwise comparisons, the researchers measured runtimes for alignment graph construction, integer program execution, linear relaxations, and the number of constraint generation iterations required to ensure valid single-trail connectivity without cycle fragmentation.
The experimental results demonstrated major performance differences, confirming severe computational hurdles in comparing genome graphs. Alignment graph construction was extremely rapid, finishing within 0.2 seconds across all graph pairs. In 168 pairs where graph traversal edit distance matched the lower bound, solving the lower-bound formulation required an average of 26 seconds, while the iterative exponential model took 71 seconds and an average of seven iterations. Solving linear relaxations averaged nine seconds for the compact model and one second for the lower bound. However, solving the compact formulation to exact integer optimality on 150-character graphs was impractical, routinely exceeding 30 minutes. Runtimes correlated positively with distance values, showing that greater sequence divergence increases optimization difficulty.
The researchers also examined synthetic three-cycle graphs with up to 32 edges simulating complex repetitive structures, including segmental duplications and translocations. On these challenging cases, the gap between graph traversal edit distance and its lower bound ranged from one to five. As this gap expanded, iterative subtour elimination runtimes escalated dramatically; at a gap of five, the iterative solver required over 15 minutes and 500 iterations. Conversely, the compact formulation solved within five seconds, showing that compact ordering constraints can outperform iterative methods when graphs feature dense overlapping cycles. Nevertheless, the authors concluded that exact methods cannot scale to bacterial or eukaryotic genomes, where viral genomes of 3000 bases already require hours. These findings establish that future progress requires developing efficient heuristic approximations.
Subject of Research: Computational complexity and integer linear programming formulations for comparing edge-labeled Eulerian genome graphs
Article Title: Revisiting the complexity of and algorithms for the graph traversal edit distance and its variants
Article References: Qiu, Y., Shen, Y., & Kingsford, C. (2024). Revisiting the complexity of and algorithms for the graph traversal edit distance and its variants. Algorithms for Molecular Biology, 19(1), Article 17. https://doi.org/10.1186/s13015-024-00262-6
Image Credits: AI Generated
DOI: 10.1186/s13015-024-00262-6
Keywords: Graph Traversal Edit Distance, Computational Complexity, NP-Completeness, Integer Linear Programming, Eulerian Trails, De Bruijn Graphs, Genome Graph Comparison, Flow-GTED, Closed-Trail Cover Traversal Edit Distance, Alignment Graphs, Subtour Elimination, Miller-Tucker-Zemlin Formulation, Hamiltonian Path Reduction, Gurobi Solver, T-Cell Receptor Sequences, Segmental Duplications, Linear Programming Relaxation
News Source: Drew Townsend. (November 14, 2026). Graph Traversal Edit Distance Is NP-Complete, Disproving Prior Polynomial Claims. Scienmag.



