# An Algebraic Approach to The Longest Path Problem

Omar Al - Khazali  Department of Mathematics & Statistics, American University
of Sharjah Department of Computer Science, American University of Sharjah
<EMAIL_ADDRESS>Department of Mathematics & Statistics, American University
of Sharjah Department of Computer Science, American University of Sharjah

###### Abstract

The Longest Path Problem is a question of finding the maximum length between
pairs of vertices of a graph. In the general case, the problem is
$\mathcal{NP}$-hard. However, there is a small collection of graph classes for
which there exists an efficient solution. Current approaches involve either
approximation or computational enumeration. For Tree-like classes of graphs,
there are approximation and enumeration algorithms which solves the problem
efficiently. We propose a new method of approaching the longest path problem
with algebraic operations and conditions that exactly identify and or
approximate the solution in polynomial time. We next introduce a ’booleanize’
mapping on the adjacency matrix of a graph which we prove identifies the
solution for trees, uniform block graphs, block graphs, and directed acyclic
graphs, with approached conditions. Finally, we display the algorithms to find
the solution, in addition to algorithms that generate all the longest paths.

Keywords—Longest Path Problem, Algebraic Graph theory, Algorithms,
Combinatorics

##  1 Introduction

The Longest Path Problem (LPP) is a well known challenge in combinatorial
optimization which is directly linked to the prominent Hamiltonian Path
Problem (HPP). In particular, the ability to solve LPP in polynomial
complexity implies the existence of efficient solutions of HPP. Specifically,
for a graph of order $n$ if there exists a path of length $n-1$ then there
exists a Hamiltonian path. More generally, HPP presents itself as a special
case of LPP [1]. Broadly, the aim is to solve LPP on a certain family of
graphs in polynomial-complexity, either by probabilistic estimation to rule
out candidate solutions, or to find the exact solution for a given class. The
main approaches to solving LPP involve approximation algorithms, or
computational enumeration/parametrized complexity.

There are existing efficient and optimal solutions, with more developments on
further classes of graphs. W. Dijkstra’s (longest path) algorithm works on
Trees in $O(n)$ time as was proven by R.W. Bulterman et al [2]. In addition, a
generalization of Dijkstra’s algorithm was introduced by R. Uehara and Y. Uno
to solve weighted trees in $O(n)$, interval biconvex graphs in
$O(n^{3}(m+n\log n))$, block graphs in $O(n+m)$, ptolemaic graphs in
$O(n(n+m))$, cacti graphs in $O(n^{2})$, and threshold graphs in $O(n+m)$ [3].
Moreover, K. Ioannidou and S. D. Nikolopoulos solved cocomparability graphs in
$O(n^{7})$ [4], and with G. B. Mertzios solved interval graphs in $O(n^{4})$
[5]. Furthermore, Y. Guo, C. Ho, M. Ko discovered a polynomial time algorithm
on distance-hereditary graphs in $O(n^{4})$ [6]. Whereby n and m are the order
and size of the graph respectively.

We introduce a separate approach to LPP which largely focuses on algebraic
conditions that exactly identify the length of the longest path. In
particular, algebraic operations which are computable in polynomial time
implies that any polynomial-sequence of these algebraic operations would be
guaranteed to be in polynomial time. Hence, this approach is unlikely to
achieve optimal solutions. However, it does provide the ability to find
polynomial time solutions to larger classes of graphs without the requirement
of weight or distance functions, nor a constraint to be defined on strictly
undirected graphs. To the author’s knowledge, there does not exist a purely
algebraic solution to LPP for any large class of graphs. In this paper, we
present a mapping which eludes to algebraic conditions to find the exact
solution, with conditions, to LPP for directed acyclic graphs, trees, uniform
block graphs, and block graphs in polynomial complexity. In addition, we
showcase the algorithms to compute the exact length in three methods for each
class of graphs with a decidable estimation parameter if only approximation is
desired. Finally, a section on path-generating algorithms is included to find
every path of the longest length.

##  2 Preliminaries

######  Definition 1.

Define a finite, simple, connected, undirected graph

$\Gamma:=(\mathbb{V}(\Gamma),\mathbb{E}(\Gamma))$

with $\mathbb{V}(\Gamma)$, and $\mathbb{E}(\Gamma)$ representing the vertex
and edge sets respectively.

######  Definition 2.

Define a finitely-sized walk $\omega$ of a graph $\Gamma$

$\omega=(v_{0},v_{1},...,v_{n}):\\{v_{i},v_{i+1}\\}\in\mathbb{E}(\Gamma)\
\forall\ i\in\mathbb{Z}_{n+1}$

Where the length of the walk is determined by the number of edges such that:

$\text{length of }\omega:=\mathfrak{L}(\omega):=|\omega|-1=n$

######  Definition 3.

Define a finitely-sized path $\gamma$ of a graph $\Gamma$ with strictly unique
elements

$\gamma=(v_{0},v_{1},...,v_{n}):\\{v_{i},v_{i+1}\\}\in\mathbb{E}(\Gamma)\land\exists!\
v_{i}\in\gamma\ \forall\ i\in\mathbb{Z}_{n+1}$

Where the length of the path in the graph counts the number of edges such
that:

$\text{length of }\gamma:=\mathscr{L}(\gamma):=|\gamma|-1=n$

######  Definition 4.

A Tree is a graph with unique paths for all vertices

$\Gamma\text{ is a Tree}\iff\exists!\ \gamma=(v_{i},...,v_{j})\ \forall\
v_{i},v_{j}\in\mathbb{V}(\Gamma)$

######  Definition 5.

A Block Graph is a graph with vertex-adjacent cliques

$\Gamma\text{ is a Block Graph}\iff\exists\ m_{i}>2:B_{i}\cong K_{m_{i}}\
\forall\ B_{i}\subseteq\Gamma\text{ maximal 2-connected}$

######  Definition 6.

A Uniform Block Graph is a Block Graph with a unique clique size for all
blocks

$\Gamma\text{ is a Uniform Block Graph}\iff\exists!\ m>2:B\cong K_{m}\
\forall\ B\subseteq\Gamma\text{ maximal 2-connected}$

######  Definition 7.

Let $\Gamma=\mathcal{D}=(\mathbb{V}(\mathcal{D}),\mathbb{E}(\mathcal{D}))$ be
a Directed Acyclic Graph (DAG) with unique paths for all vertices

$\mathcal{D}\text{ is a }DAG\iff\exists!\ \gamma=(v_{i},...,v_{j})\ \forall\
v_{i},v_{j}\in\mathbb{V}(\mathcal{D}):(v_{i},v_{j})\in\mathbb{E}(\mathcal{D})\land(v_{j},v_{i})\notin\mathbb{E}(\mathcal{D})$

######  Definition 8.

Let $A$ be a mapping that generates the Adjacency Matrix of $\Gamma$

$\displaystyle A:\\{(\mathbb{V},\mathbb{E})\ |\
\mathbb{E}\subseteq\mathbb{V}\times\mathbb{V}\\}\longrightarrow\mathbb{M}_{|\mathbb{V}|\times|\mathbb{V}|}$
$A(\Gamma)_{i,j}:=\begin{cases}1&,\ \ (v_{i},v_{j})\in\mathbb{E}(\Gamma)\\\
0&,\ \ (v_{i},v_{j})\notin\mathbb{E}(\Gamma)\\\ \end{cases}\ \forall\
i,j\in\mathbb{Z}_{|\mathbb{V}(\Gamma)|+1}^{*}$

######  Definition 9.

Let $\partial(u,v)$ be the minimal length between two vertices in $\Gamma$

$\partial(u,v):=min\\{\mathscr{L}(\gamma)\ |\
\gamma=(u,...,v),u,v\in\mathbb{V}(\Gamma)\\}$

######  Definition 10.

Define $\omega(\Gamma)$ as the order of the largest completely connected
subgraph of $\Gamma$

$\omega(\Gamma):=max\\{|\mathbb{V}(G)|\ |\ G\subseteq\Gamma\land\exists\
m\in\mathbb{N}:G\cong K_{m}\\}$

######  Definition 11.

Define a map, $\beta$, to booleanize any matrix to a (0,1)-matrix as follows

$\beta:\mathbb{M}_{n\times n}\longrightarrow\mathbb{M}_{n\times n}^{(0,1)}$
$\beta(Q)_{i,j}:=min\\{1,Q_{i,j}\\}:Q\in\mathbb{M}_{n\times n}$

reducing non-zero valued entries to 1, and zero valued entries kept as 0 to
transform the matrix $A$ to a binary-entry matrix $\beta(Q)_{i,j}\in\\{0,1\\}\
\forall\ i,j\in\mathbb{Z}_{n}$

The interest is to use this transformation on results of multiplicative matrix
operations. Currently, the algorithm with the optimal complexity is in
$\Theta(n^{2.3728596})$. However, given that the algorithm is galactic, in
realistic implementations, Strassen’s algorithm would be used which is in
$\Theta(n^{log_{2}7})\simeq\Theta(n^{2.807})$ [7]. With the goal of minimizing
the complexity of the booleanization operation, method of computation is
detailed below for the coming algorithms. Hence, here is a faster method of
computation. Firstly, note that

$\displaystyle\begin{aligned} \ \ \beta(X\times
Y)_{i,j}=min&\left\\{1,\sum_{k=1}^{n}X_{i,k}\cdot
Y_{k,j}\right\\}:X,Y\in\mathbb{M}_{n\times n}\end{aligned}$
$\displaystyle\begin{aligned} \beta(X\times Y)_{i,j}=0&\iff X_{i,k}=0\lor
Y_{k,j}=0\ \forall\ k\in\mathbb{Z}_{n+1}^{*}\\\ \beta(X\times
Y)_{i,j}=1&\iff\exists\ k\in\mathbb{Z}_{n+1}^{*}:X_{i,k}>0\land
Y_{k,j}>0\end{aligned}$

######  Definition 12.

Let $\mathbb{B}=\prod_{i=1}^{\eta}(\mathbb{Z}_{2})$ be the set of binary
numbers$,\land,+:\mathbb{B}\times\mathbb{B}\longrightarrow\mathbb{B},a,b\in\mathbb{B}$,

$(a\land b)_{i}:=a_{i}\land b_{i}\ \forall\ i\in\mathbb{Z}_{\eta+1}^{*}$
$(a+b)_{i}:=(a+b)_{i-1}+a_{i}+b_{i}\ \forall\ i\in\mathbb{Z}_{\eta+1}^{*}$

######  Lemma 1.

The booleanized product can be computed equivalently with $\land$ by

$\beta(A(\Gamma)^{2})_{i,j}=\begin{cases}1,&f(A(\Gamma)_{i,-})\land
f(A(\Gamma)_{-,j})>0\\\ 0,&f(A(\Gamma)_{i,-})\land f(A(\Gamma)_{-,j})=0\\\
\end{cases}$

###### Proof.

$(a\land b)=0\iff a_{k}=0\lor b_{k}=0\ \forall\ k\in\mathbb{N}$ $(a\land
b)>0\iff\exists\ k\in\mathbb{N}:a_{k}=1\land b_{k}=1$ $\text{Since
}A(\Gamma)_{i,j}\in\\{0,1\\}\ \forall\
i,j\in\mathbb{Z}_{n+1}^{*}\implies\exists\
A(\Gamma)_{i,-}\xmapsto{f}a\in\mathbb{B},A(\Gamma)_{-,j}\xmapsto{f}b\in\mathbb{B}$
$\text{where }A(\Gamma)_{i,-},A(\Gamma)_{-,j}\text{ are the }i^{th}\text{ Row
and }j^{th}\text{ Column vectors respectively}$
$\therefore\beta(A(\Gamma)^{2})_{i,j}=min\left\\{1,\sum_{k=1}^{n}A(\Gamma)_{i,k}\cdot
A(\Gamma)_{k,j}\right\\}=\begin{cases}1,&f(A(\Gamma)_{i,-})\land
f(A(\Gamma)_{-,j})>0\\\ 0,&f(A(\Gamma)_{i,-})\land f(A(\Gamma)_{-,j})=0\\\
\end{cases}$

∎

Given that bitwise operations are computable in $\Theta(1)$ or some
$\Theta(\delta)$ where $\delta$ depends on the number of bytes of an integer.
That reduces the complexity of computing the booleanization of a matrix
product to $\Theta(\delta n^{2})$. Allowing us to reduce the complexity of the
algorithms pertaining to the Length of the Longest Path. Specifically
referring to Algorithms 2, 3, 4, 5, 6, 7, 8, 9, and 10. While Algorithm 1
defines the process of using the above method to compute a booleanized matrix
product.

Algorithm 1 Booleanization Algorithm & Computing $\beta(A(\Gamma_{1})\times
A(\Gamma_{2}))$

1:$\Gamma_{1}:=(\mathbb{V}(\Gamma),\mathbb{E}(\Gamma_{1}))$

2:$\Gamma_{2}:=(\mathbb{V}(\Gamma),\mathbb{E}(\Gamma_{2}))$

3:for $i\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

4: for $j\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

5: if $A(\Gamma_{1})_{i,j}=1\land A(\Gamma_{2})_{j,i}=1$ then

6: $A(\Gamma)_{i,-}\leftarrow A(\Gamma)_{i,-}+2^{j}$

7: $A(\Gamma)_{-,j}\leftarrow A(\Gamma)_{-,j}+2^{i}$

8:for $i\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

9: for $j\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

10: if $A(\Gamma)_{i,-}\land A(\Gamma)_{-,j}>0$ then

11: $R_{i,j}\leftarrow 1$

12:$\textbf{return}\ R$

######  Lemma 2.

The number of walks from $v_{i}$ to $v_{j}$ can be found by

$|\\{\omega=(v_{i},...,v_{j})\ |\
\mathfrak{L}(\omega)=k:v_{i},v_{j}\in\mathbb{V}(\Gamma)\\}|=A(\Gamma)^{k}_{i,j}$

###### Proof.

The result is true for $p$ = 0 $\because A(\Gamma)^{0}=I$. Suppose the result
is true for $p=n$, we now prove for $p=n+1$. We see that the set of walks of
length $n+1$ from $v_{i}$ to $v_{j}$ has the cardinality of the set of walks
of length $n$ from $v_{i}$ to $v_{k}\in N(v_{j})$. Thus we count the number of
walks by:

$\sum_{\\{v_{k},v_{j}\\}\in\mathbb{E}(\Gamma)}A(\Gamma)_{i,k}^{n}=\sum_{k=1}^{|\mathbb{V}(\Gamma)|}A(\Gamma)^{n}_{i,k}\cdot
A(\Gamma)_{k,j}=A(\Gamma)^{p}_{i,j}=A(\Gamma)^{n+1}_{i,j}$

Since $A(\Gamma)_{k,j}=1\iff\exists\ \\{v_{k},v_{j}\\}\in\mathbb{E}(\Gamma)$
and otherwise for $A(\Gamma)_{k,j}=0$. Hence, only counting for when there
exists an edge to add to the walk of length $n+1$. ∎

######  Lemma 3.

Let $\Gamma=(\mathbb{V}(\Gamma),\mathbb{E}(\Gamma))$ be a simple, undirected,
finite tree. Then,

$\beta(A(\Gamma)^{n})_{i,j}=1\iff\exists\ \gamma=(v_{i},...,v_{j})\land
n\in\\{\mathscr{L}(\gamma)+2k\ |\ k\in\mathbb{N}\\}$

###### Proof.

Let $\partial(u,v)$ denote the minimal path length

$\displaystyle\Gamma\text{ acyclic}\implies A(\Gamma)^{n}_{i,j}>0\iff\exists\
\omega=(v_{i},...,v_{j})$ $\displaystyle\land\nexists\ G\subseteq\Gamma:u\in
G\cong K_{2m+1}\forall\
u\in\mathbb{V}(\Gamma)\implies\mathfrak{L}(\omega)=\partial(v_{i},v_{j})+2k:k\in\mathbb{N}$
$\displaystyle\implies\text{to go from }v_{j}\longrightarrow v_{j},\text{
there must be two steps to loop back
}v_{j}\xrightarrow{}u\xrightarrow{}v_{j}:u\in N(v_{j})$
$\displaystyle\therefore$ $\displaystyle\text{ since }\exists!\
\gamma=(u,...,v)\ \forall\
u,v\in\mathbb{V}(\Gamma)\implies\mathscr{L}(\gamma)=\partial(u,v)\implies\mathfrak{L}(\omega)=n=\mathscr{L}(\gamma)+2k$
$\displaystyle\implies
A(\Gamma)^{n}_{i,j}>0\iff\beta(A(\Gamma)^{n})_{i,j}=1\iff
n\in\left\\{\mathscr{L}(\gamma)+2k\ |\ k\in\mathbb{N}\right\\}$

Proof. $\Longleftarrow$

$\displaystyle\exists\ \gamma=(v_{i},...,v_{j})\land
n\in\\{\mathscr{L}(\gamma)+2k\ |\ k\in\mathbb{N}\\}\implies\exists\
\omega=(v_{i},...,v_{j})$ $\displaystyle\land\nexists\ G\subseteq\Gamma:u\in
G\cong K_{2m+1}\forall\
u\in\mathbb{V}(\Gamma)\implies\mathfrak{L}(\omega)=\partial(v_{i},v_{j})+2k:k\in\mathbb{N}$
$\displaystyle\therefore$ $\displaystyle\text{ since }\exists!\
\gamma=(u,...,v)\ \forall\
u,v\in\mathbb{V}(\Gamma)\implies\mathscr{L}(\gamma)=\partial(u,v)\implies\mathfrak{L}(\omega)=n=\mathscr{L}(\gamma)+2k$
$\displaystyle\implies\exists\
\omega=(v_{i},...,v_{j}):\mathfrak{L}(\omega)=n\implies
A(\Gamma)^{n}_{i,j}=1\implies\beta(A(\Gamma)^{n})_{i,j}=1$

∎

##  3 The Longest Path Problem

######  Theorem 1.

Let $\Gamma$ be a Tree, then TFAE:

  1. 1.

The length of the Longest Path of $\Gamma$ is n

  2. 2.

$\beta(A(\Gamma)^{n+1})=\beta(A(\Gamma)^{n-1}):$ n is the minimum such number

Equivalently, to compute the value, define a map $\mathfrak{D}$

$\mathfrak{D}:\\{(\mathbb{V},\mathbb{E})\ |\
\mathbb{E}\subset\mathbb{V}\times\mathbb{V},\exists!\ \gamma=(u,..,v)\
\forall\ u,v\in\mathbb{V}\\}\longrightarrow\mathbb{N}_{0}\cup\\{-1\\}$

The Length of the Longest Path is found by the following

$\mathfrak{D}(\Gamma)=min\\{n\ |\
\beta(A(\Gamma)^{n+1})=\beta(A(\Gamma)^{n-1})\ \forall\
n\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}$

The logical interpretation is that if some matrix for a $\beta$-operated
$A(\Gamma)^{n+1}$ is equal to a previously calculated $\beta$-operated
$A(\Gamma)^{n-1}$, then the minimum $n\in\mathbb{N}_{0}$ for which that
property is true is the longest path. Which follows with an equivalent
statement whereby:

$k\geq\mathfrak{D}(\Gamma)\iff\beta(A(\Gamma)^{k+1})=\beta(A(\Gamma)^{k-1})$

###### Proof.

### $1\implies 2$

Assume $\mathfrak{D}(\Gamma)=n\therefore\forall\ u,v\in\mathbb{V}(\Gamma)\
\nexists\ \gamma=(u,...,v):\mathscr{L}(\gamma)=n+1$. Hence, by Lemma 2 and 3,
we can see that between any pair of vertices we have a walk for any
$u,v\in\mathbb{V}(\Gamma)\ \exists\
\omega=(u,...,v):\mathfrak{L}(\omega)=n+1\iff\exists\
\Omega\subset\omega:\mathfrak{L}(\Omega)=n-1$. Then clearly, since
$\beta(A(\Gamma))$ shows the existence of a walk and path,
$\beta(A(\Gamma)^{n+1})=\beta(A(\Gamma)^{n-1})$. ∎

###### Proof.

### $2\implies 1$

Assume $\exists\ k:\beta(A(\Gamma)^{k+1})=\beta(A(\Gamma)^{k-1})$ where $k$ is
the minimum such number to satisfy this property. Additionally, assume that
$\mathfrak{D}(\Gamma)=n$ where $k\neq n$. Deny the statement, let $k\neq n$.
By $1\implies 2$ we know that since
$\beta(A(\Gamma)^{k+1})=\beta(A(\Gamma)^{k-1})$ then $k>\mathfrak{D}(\Gamma)$.
However, since $k$ is the minimum such number, and $k\neq n$, the assumption
is false. Thus, $k=n$. ∎

######  Corollary 1.1.

Let $\Gamma$ be a Tree, let $v_{i},v_{j}\in\gamma_{\mathfrak{D}}$ where
$\gamma_{\mathfrak{D}}$ is the longest path, then

$\displaystyle\exists\
i,k\in\mathbb{Z}_{|\mathbb{V}(\Gamma)|+1}^{*}:(\beta(A(\Gamma)^{n+1})-\beta(A(\Gamma)^{n-1}))_{i,j}=1$
$\displaystyle\ \ \ \ \ \ \land\exists\
(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-2}))_{i,k}=1:\\{v_{k},v_{j}\\}\in\mathbb{E}(\Gamma)\iff(v_{k},v_{j})\subseteq\gamma_{\mathfrak{D}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ :\partial(v_{i},v_{k})=n\land\partial(v_{i},v_{j})=n+1\
\forall\ n\in\mathbb{Z}_{\mathfrak{D}(\Gamma)}$

###### Proof.

Let $P_{t}(c)=\\{\gamma=(u,...,w)\ |\ \mathscr{L}(\gamma)\in\\{c\bmod 2,c\bmod
2+2,c\bmod 2+4,...,c\\}\\}:c\in\mathbb{N}$

$\displaystyle\text{Assume
}(\beta(A(\Gamma)^{n+1})-\beta(A(\Gamma)^{n-1}))_{i,j}=1\land(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-2}))_{i,k}=1\land\\{v_{k},v_{j}\\}\in\mathbb{E}(\Gamma)$
$\displaystyle\text{By Lemma 3, }\forall\
\beta(A(\Gamma)^{n+1})_{p,q}=1,\exists\ \gamma=(v_{p},...,v_{q})\in
P_{t}(n+1)$ $\displaystyle\text{Likewise, }\forall\
\beta(A(\Gamma)^{n-1})_{p,q}=1,\exists\ \gamma=(v_{p},...,v_{q})\in
P_{t}(n-1)$ $\displaystyle\therefore\forall\
(\beta(A(\Gamma)^{n+1})-\beta(A(\Gamma)^{n-1}))_{i,j}=1,\exists\
\gamma_{i,j}\in P_{t}(n+1)\setminus
P_{t}(n-1):\mathscr{L}(\gamma_{i,j})=n+1=\partial(v_{i},v_{j})$
$\displaystyle\text{Similarly, }\forall\
(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-2}))_{i,k}=1,\exists\ \gamma_{i,k}\in
P_{t}(n)\setminus
P_{t}(n-2):\mathscr{L}(\gamma_{i,k})=n=\partial(v_{i},v_{k})$
$\displaystyle\text{Since }\\{v_{k},v_{j}\\}\in\mathbb{E}(\Gamma)\iff\exists\
\gamma_{i,k}\in P_{t}(n)\setminus P_{t}(n-2)\land\gamma_{i,j}\in
P_{t}(n+1)\setminus P_{t}(n-1):\gamma_{i,j}=\gamma_{i,k}\cup(v_{j})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\iff(v_{k},v_{j})\subseteq\gamma_{i,j}\subseteq\gamma_{\mathfrak{D}}$

∎

######  Theorem 2.

Let $\Gamma$ be a Uniform Block Graph, then TFAE:

  1. 1.

The length of the Longest Path of $\Gamma$ is
$n\cdot(\omega(\Gamma)-1)=n\cdot(m-1)$

  2. 2.

$\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}:$ n is the minimum such number

whereby, $J_{|\mathbb{V}(\Gamma)|}$ is a square matrix of all 1’s with size
$|\mathbb{V}(\Gamma)|^{2}$. Equivalently, to compute the value, define a map
$\mathscr{LP}$

$\mathscr{LP}:\\{\Gamma=(\mathbb{V},\mathbb{E})\ |\ \exists!\ m>2:B\cong
K_{m}\ \forall\ B\subseteq\Gamma\text{ maximal
2-connected}\\}\longrightarrow\mathbb{N}_{0}\cup\\{-1\\}$

The Length of the Longest Path is found by the following

$\displaystyle\mathscr{LP}(\Gamma)$ $\displaystyle=min\\{n\ |\
\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}\ \forall\
n\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}\cdot(\omega(\Gamma)-1)$
$\displaystyle=min\\{n\ |\ \beta(A(\Gamma)^{n})_{i,j}=1\ \forall\
n,i,j\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}\cdot(m-1)$

###### Proof.

### $1\implies 2$

Assume $\mathscr{LP}(\Gamma)=n\cdot(m-1)$ is the length of the longest path.

Define
$M:=\\{v_{1},v_{2},...,v_{d}\\}:\text{deg}(v_{i})=\Delta(\Gamma)=2(m-1)$.
Hence, by construction we know $M$ is a vertex separator of $\Gamma$. Thus, we
have the result:

$\displaystyle\forall\ \mathbb{V}(B_{p})\cap\mathbb{V}(B_{q})\neq\phi,\
\exists!v_{i}\in M$
$\displaystyle:\\{v_{i}\\}=\mathbb{V}(B_{p})\cap\mathbb{V}(B_{q})\ \forall\
B_{p},B_{q}\subseteq\Gamma\text{ maximal 2-connected}$
$\displaystyle\implies\bigcup_{i=1}^{d}N(v_{i})\cup M=\mathbb{V}(\Gamma)$

Let $\partial(u,w)=min\\{\mathscr{L}(\gamma)\ |\
\gamma=(u,...,v),u,v\in\mathbb{V}(\Gamma)\\}$ denote the minimal path length
between $u,w\in\mathbb{V}(\Gamma)$. Then the form of any (minimal) length path
by:

$\displaystyle\gamma_{uw}^{min}=(u,..$
$\displaystyle.,w):\mathscr{L}(\gamma_{uw}^{min})=\partial(u,w):u,w\in\mathbb{V}(\Gamma)$
$\displaystyle\implies\exists\ v_{u},v_{w}\in M:u\in N(v_{u}),w\in N(v_{w})$
$\displaystyle\implies\gamma_{uw}^{min}=(u,v_{u},v_{i},...,v_{k},...,v_{j},v_{w},w):v_{i},v_{k},v_{j}\in
M$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \land v_{i}\in
N(v_{u}),v_{j}\in N(v_{w})\ \forall\ u,w\in\mathbb{V}(\Gamma)$

We can see that the longest (minimal) path $\gamma_{l}^{min}$ must have:

$\displaystyle\exists\ v_{a},v_{b}\in M:\gamma_{l}^{min}=(a_{l}$
$\displaystyle,v_{a},...,v_{b},b_{l}):\mathscr{L}(\gamma)=\partial(a_{l},b_{l})\land
a_{l}\in N(v_{a}),b_{l}\in N(v_{b})$
$\displaystyle\implies\partial(a_{l},b_{l})=\partial(v_{a},v_{b})+2$

Which leads to the form of the longest path $\gamma_{l}^{max}$ which must
have:

$\displaystyle\exists\ v_{a},v_{b}\in M:\gamma_{l}^{max}$ $\displaystyle=\
(\underbrace{a_{l},r_{1},r_{2},...,r_{m-2}}_{m-1\text{ elements }\in
N(v_{a})\cap\mathbb{V}(B_{a})},v_{a},...,v_{k},...,v_{b},\underbrace{t_{m-2},...,t_{2},t_{1},b_{l}}_{m-1\text{
elements }\in N(v_{b})\cap\mathbb{V}(B_{b})})$
$\displaystyle:a_{l},b_{l}\in\gamma_{l}^{min}\ \forall\ r_{i}\in
N(v_{a}),t_{j}\in N(v_{b})\text{ which forms the same }\forall\ v_{k}\in M$
$\displaystyle=(\underbrace{\left[N(v_{a})\cap\mathbb{V}(B_{a})\right]}_{m-1\text{
elements}},v_{a},...,v_{k-1},\underbrace{\left[N(v_{k})\cap\mathbb{V}(B_{k})\right]}_{m-1\text{
elements}},v_{k},...,v_{b},\underbrace{\left[N(v_{b})\cap\mathbb{V}(B_{b})\right]}_{m-1\text{
elements}})$ $\displaystyle\text{ following the cardinality of
}\gamma_{l}^{min}\implies 1\leq
k\leq\partial(a_{l},b_{l})=\partial(v_{a},v_{b})+2$
$\displaystyle\therefore\mathscr{L}(\gamma_{l}^{max})=\partial(a_{l},b_{l})\cdot(m-1)$

Given that we assumed $\mathscr{LP}(\Gamma)=n\cdot(m-1)$ Then we have

$\mathscr{LP}(\Gamma)=n\cdot(m-1)=\mathscr{L}(\gamma_{l}^{max})=\partial(a_{l},b_{l})\cdot(m-1)\implies
n=\partial(a_{l},b_{l})$

Consequently, since every vertex $u$ belongs to a $K_{3}$ subgraph of their
block $B_{u}$, then

$\displaystyle\forall\ u,w\in\mathbb{V}(\Gamma),\exists\
B_{u},B_{w}\subseteq\Gamma$ $\displaystyle\text{ maximal
2-connected}:B_{u}\cong B_{w}\cong K_{m}$ $\displaystyle\implies\exists\
T_{u}\subseteq B_{u}\land T_{w}\subseteq B_{w}:T_{u}\cong T_{w}\cong
K_{3}:u\in T_{u}\land w\in T_{w}$

Implying that we can always find a walk of length $\partial(a_{,}b_{l})=n$ for
any pair of vertices

$\displaystyle\omega=(u,u_{T},...,w_{T},w):\ $
$\displaystyle\mathfrak{L}(\omega)=\partial(a_{l},b_{l})=n,u_{T}\in
T_{u},w_{T}\in T_{w}\ \forall\ u,w\in\mathbb{V}(\Gamma)$
$\displaystyle\implies\exists\ \omega=(u,...,w):\mathfrak{L}(\omega)=n\
\forall\ u,w\in\mathbb{V}(\Gamma)$
$\displaystyle\implies\beta(A(\Gamma)^{n})_{i,j}=1\ \forall\
i,j\in\mathbb{Z}_{|\mathbb{V}(\Gamma)|+1}^{*}$
$\displaystyle\implies\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}$

We conclude that $n$ is the minimum such number since

$\displaystyle\exists\ \omega=\gamma_{l}^{min}:$ $\displaystyle\
\mathfrak{L}(\omega)=\mathscr{L}(\gamma_{l}^{min})=n=\partial(a_{l},b_{l})$
$\displaystyle\ \ \ \ \ \
\implies\beta(A(\Gamma)^{n-1})=\beta(A(\Gamma)^{\partial(a_{l},b_{l})-1})\neq
J_{|\mathbb{V}(\Gamma)|}$

∎

###### Proof.

### $2\implies 1$

Assume $\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}:n$ is the minimum such
number. Therefore we know that:

$\exists\ \omega=(u,...,w):\mathfrak{L}(\omega)=n\ \forall\ u,w\in\mathbb{V}$

From the proof of $1\implies 2$, we know that for $\gamma_{l}^{min}$, we have:

$\displaystyle\gamma_{l}^{min}=(a_{l},...,b_{l}):\mathscr{L}(\gamma_{l}^{min})=\partial(a_{l},b_{l})=n$

Similarly from $1\implies 2$ we know for $\gamma_{l}^{max}$ we have:

$\displaystyle\gamma_{l}^{max}$ $\displaystyle=\
(\underbrace{a_{l},r_{1},r_{2},...,r_{m-2}}_{m-1\text{ elements }\in
N(v_{a})\cap\mathbb{V}(B_{a})},v_{a},...,v_{k},...,v_{b},\underbrace{t_{m-2},...,t_{2},t_{1},b_{l}}_{m-1\text{
elements }\in N(v_{b})\cap\mathbb{V}(B_{b})})$
$\displaystyle:a_{l},b_{l}\in\gamma_{l}^{min}\ \forall\ r_{i}\in
N(v_{a}),t_{j}\in N(v_{b})\text{ which forms the same }\forall\ v_{k}\in M$
$\displaystyle=(\underbrace{\left[N(v_{a})\cap\mathbb{V}(B_{a})\right]}_{m-1\text{
elements}},v_{a},...,v_{k-1},\underbrace{\left[N(v_{k})\cap\mathbb{V}(B_{k})\right]}_{m-1\text{
elements}},v_{k},...,v_{b},\underbrace{\left[N(v_{b})\cap\mathbb{V}(B_{b})\right]}_{m-1\text{
elements}})$ $\displaystyle\text{ following the cardinality of
}\gamma_{l}^{min}\implies 1\leq
k\leq\partial(a_{l},b_{l})=\partial(v_{a},v_{b})+2$
$\displaystyle\therefore\mathscr{L}(\gamma_{l}^{max})=\partial(a_{l},b_{l})\cdot(m-1)$

Finally, using the fact that $n=\partial(a_{l},b_{l})$ we end up with:

$\displaystyle n=\partial(a_{l},b_{l})$ $\displaystyle\implies
n\cdot(m-1)=\partial(a_{l},b_{l})\cdot(m-1)=\mathscr{L}(\gamma_{l}^{max})$
$\displaystyle\implies\mathscr{L}(\gamma_{l}^{max})=\mathscr{LP}(\Gamma)=n\cdot(m-1)$

∎

######  Definition 13.

Define a chain, $\mathcal{C}$ of a Block Graph, $\Gamma$, to be a sequence of
blocks

$\mathcal{C}=(B_{1},B_{2},...,B_{|\mathcal{C}|}):B_{k}\subseteq\Gamma\text{
maximal 2-connected}\ \forall\ B_{k}\in\mathcal{C}$

######  Corollary 2.1.

The length of the longest chain
$\mathcal{C}_{l}=(B_{1},B_{2},...,B_{|\mathcal{C}_{l}|})$ can be found by:

$\displaystyle|\mathcal{C}_{l}|$ $\displaystyle=min\\{n\ |\
\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}\ \forall\
n\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}$ $\displaystyle=min\\{n\ |\
\beta(A(\Gamma)^{n})_{i,j}=1\ \forall\
n,i,j\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}$

###### Proof.

From $1\implies 2$ of the Theorem 2 on Uniform Block Graphs, we know

$\displaystyle\gamma_{l}^{min}$
$\displaystyle=(a_{l},v_{a},...,v_{b},b_{l}):\mathscr{L}(\gamma)=\partial(a_{l},b_{l})\land
a_{l}\in N(v_{a}),b_{l}\in N(v_{b})$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \implies a_{l},v_{a}\in B_{1},b_{l},v_{b}\in B_{s}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \implies
v_{k}\in B_{k-1}\land v_{k}\in B_{k}\ \forall\ v_{k}\in\gamma_{l}^{min}$

Therefore we can see that for blocks $B_{2},...,B_{\partial(a_{l},b_{l})-1}$
each contains two $v_{k-1},v_{k}$ whereby:

$\displaystyle 2\leq k\leq\partial(a_{l},b_{l})-1\implies\exists\
v_{k-1},v_{k}\in\gamma_{l}^{min}:v_{k-1},v_{k}\in B_{k}$

Not counting blocks $B_{1},B_{\partial(a_{l},b_{l})}$ since they are the
’leaf’ blocks of $\Gamma$, they only have a single $v_{1}\in
B_{1},v_{\partial(a_{l},b_{l})}\in B_{\partial(a_{l},b_{l})}$. We also know we
can count every block using $\gamma_{l}^{min}$ since $\exists\
v\in\gamma_{l}^{min}\ \forall\ v\in B_{v}$ for some $B_{v}\in\mathcal{C}_{l}$.
Hence, we can see that the number of blocks corresponds directly to:

$|\mathcal{C}_{l}|=2+\sum_{\forall
v_{k}\in\gamma_{l}^{min}\setminus\\{v_{1},v_{\partial(a_{l},b_{l})}\\}}1=\underbrace{2}_{\text{for
}k\in\\{1,\partial(a_{l},b_{l})\\}}+\underbrace{\sum_{i=2}^{\partial(a_{l},b_{l})-1}1}_{\text{for
}2\leq k\leq\partial(a_{l},b_{l})-1}=\partial(a_{l},b_{l})$

From $1\implies 2$ of Theorem 2 on Uniform Block Graphs we know that
$n=\partial(a_{l},b_{l})$ is the minimum number for which
$\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}$. Therefore, we can conclude
that

$\displaystyle|\mathcal{C}_{l}|=\partial(a_{l},b_{l})$ $\displaystyle=min\\{n\
|\ \beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}\ \forall\
n\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}$ $\displaystyle=min\\{n\ |\
\beta(A(\Gamma)^{n})_{i,j}=1\ \forall\
n,i,j\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}$

∎

Since Corollary 2.1 provides the length of the longest chain of blocks, as can
be seen from the proof, nothing is restricting us to a single unique clique
for all blocks. Therefore, we can use it for Block Graphs too, though the
algorithm will have to work differently with a worse asymptotic complexity
compared to Uniform Block Graphs. In particular, given that Uniform Block
Graphs have chains with unique cliques of order $m$, then there is no
requirement to compute the order of every approached block in a chain.
Meanwhile, Block Graphs have non-unique clique chains. Therefore we require a
method to compute the order of the clique for every clique in the longest
chain, which hence increases the computational complexity when generalizing to
Block Graphs. This is why a distinction is made for results on Uniform Block
Graphs versus Block Graphs.

######  Lemma 4.

Let $\Gamma$ be a Block Graph, then

$(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{m}))_{i,j}=1\iff\exists\
\gamma=(v_{i},...,v_{j}):\mathscr{L}(\Gamma)\in\\{m+1,...,n\\}:m<n$

###### Proof.

$\displaystyle\beta(A(\Gamma)^{n})_{i,j}=1\iff\exists\
\omega_{i,j}=(v_{i},...,v_{j}):\mathcal{L}(\omega_{i,j})=n\iff\exists\
\gamma_{i,j}=(v_{i},...,v_{j}):\mathscr{L}(\gamma_{i,j})\leq\mathcal{L}(\omega_{i,j})$
$\displaystyle\land\ $ $\displaystyle\beta(A(\Gamma)^{m})_{p,q}=1\iff\exists\
\omega_{p,q}=(v_{p},...,v_{q}):\mathcal{L}(\omega_{p,q})=m\iff\exists\
\gamma_{p,q}=(v_{p},...,v_{q}):\mathscr{L}(\gamma_{p,q})\leq\mathcal{L}(\omega_{p,q})$
$\displaystyle\therefore\ $
$\displaystyle(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{m}))_{i,j}=1\iff\exists\
\omega\ =(v_{i},...,v_{j}):\mathcal{L}(\omega)=n:m<n$ $\displaystyle\ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\iff\exists\
\gamma_{n}=(v_{i},...,v_{j}):\mathscr{L}(\gamma_{n})\leq\mathcal{L}(\omega_{i,j})=n$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \
\land\mathscr{L}(\gamma_{n})\nleq\mathcal{L}(\omega_{p,q})=m\implies
m<\mathscr{L}(\gamma_{n})\leq n$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\iff\mathscr{L}(\gamma_{n})\in\\{m+1,...,n\\}$

∎

######  Theorem 3.

Let $\Gamma$ be a Block Graph, and
$\mathscr{LP}:\\{\Gamma=(\mathbb{V},\mathbb{E})\ |\ \exists\
m\in\mathbb{N}:B\cong K_{m}:m>2\ \forall\ B\subseteq\Gamma\ \text{ maximal
2-connected}\\}\longrightarrow\mathbb{N}\cup\\{-1\\}$ be the length of the
Longest Path of a given Block Graph, then

$\displaystyle\mathscr{LP}(\Gamma)=\sum_{n=1}^{\mathcal{L}}\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=1}^{|\mathbb{V}(\Gamma)|}\left(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-1})\right)_{i,j}:\mathcal{L}=min\\{k\
|\ \beta(A(\Gamma)^{k})=J_{|\mathbb{V}(\Gamma)|}\\}$

###### Proof.

From the proof of Theorem 2 and Corollary 2.1, we can see with a change to $m$
accounting for dependency on every $B\subseteq\Gamma\text{ maximal
2-connected}$ we have

$\displaystyle\gamma_{l}^{max}$ $\displaystyle=\
(\underbrace{a_{l},r_{1},r_{2},...,r_{|\mathbb{V}(B_{a})|-2}}_{|\mathbb{V}(B_{a})|-1\text{
elements }\in
N(v_{a})\cap\mathbb{V}(B_{a})},v_{a},...,v_{k},...,v_{b},\underbrace{t_{|\mathbb{V}(B_{b})|-2},...,t_{2},t_{1},b_{l}}_{|\mathbb{V}(B_{b})|-1\text{
elements }\in N(v_{b})\cap\mathbb{V}(B_{b})})$
$\displaystyle:a_{l},b_{l}\in\gamma_{l}^{min}\ \forall\ r_{i}\in
N(v_{a}),t_{j}\in N(v_{b})\text{ which forms the same }\forall\ v_{k}\in M$
$\displaystyle=(\underbrace{\left[N(v_{a})\cap\mathbb{V}(B_{a})\right]}_{|\mathbb{V}(B_{a})|-1\text{
elements}},v_{a},...,v_{k-1},\underbrace{\left[N(v_{k})\cap\mathbb{V}(B_{k})\right]}_{|\mathbb{V}(B_{k})|-1\text{
elements}},v_{k},...,v_{b},\underbrace{\left[N(v_{b})\cap\mathbb{V}(B_{b})\right]}_{|\mathbb{V}(B_{b})|-1\text{
elements}})$ $\displaystyle\text{ following the cardinality of
}\gamma_{l}^{min}\implies 1\leq
k\leq\partial(a_{l},b_{l})=\partial(v_{a},v_{b})+2$
$\displaystyle\therefore\mathscr{L}(\gamma_{l}^{max})=|\mathbb{V}(B_{1})|-1+|\mathbb{V}(B_{2})|-1+...+|\mathbb{V}(B_{\partial(a_{l},b_{l})})|-1$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=\sum_{i=1}^{\partial(a_{l},b_{l})}(|\mathbb{V}(B_{i})|-1)\underbrace{=\sum_{n=1}^{\partial(a_{l},b_{l})}\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=1}^{|\mathbb{V}(\Gamma)|}\left(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-1})\right)_{i,j}}_{\text{implied
by Lemma 4}}$ $\displaystyle\text{Corollary 2.1 implies
}\partial(a_{l},b_{l})=min\\{n\ |\
\beta(A(\Gamma)^{n})=J_{|\mathbb{V}(\Gamma)|}\ \forall\
n\in\mathbb{Z}_{|\mathbb{E}(\Gamma)|+1}^{*}\\}=\mathcal{L}$
$\displaystyle\implies\mathcal{L}=\partial(a_{l},b_{l})\implies\mathscr{LP}(\Gamma)=\sum_{n=1}^{\mathcal{L}}\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=1}^{|\mathbb{V}(\Gamma)|}\left(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-1})\right)_{i,j}$

∎

######  Theorem 4.

Let $\mathcal{D}$ be a Directed Acyclic Graph, then TFAE:

  1. 1.

The length of the Longest Path of $\mathcal{D}$ is $n$

  2. 2.

$\beta(A(\mathcal{D})^{n})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D}|}:$
n is the minimum such number

Equivalently, to compute the value, define a map $\mathfrak{D}_{{}_{dag}}$

$\mathfrak{D}_{{}_{dag}}:\\{\mathcal{D}=(\mathbb{V},\mathbb{E})\ |\
\mathcal{D}\text{ is a }DAG\\}\longrightarrow\mathbb{N}_{0}\cup\\{1\\}$

The Length of the Longest Path is found by the following

$\mathfrak{D}_{{}_{dag}}(\mathcal{D})=min\\{n\ |\
\beta(A(\mathcal{D})^{n})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}\forall\
n\in\mathbb{Z}_{|\mathbb{E}(\mathcal{D}|+1}^{*}\\}$

Following the logic of Trees. However since the walks are directed and the
matrix $A(\mathcal{D})$ is nilpotent. The index of $A(\mathcal{D})$ would be
the length of longest path. Therefore, equivalently

$k\geq\mathfrak{D}_{{}_{dag}}(\mathcal{D})\iff\beta(A(\mathcal{D})^{k})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$

###### Proof.

### $1\implies 2$

Assume $\mathfrak{D}_{{}_{dag}}(\mathcal{D})=n\ \therefore\forall\
u,v\in\mathbb{V}(\mathcal{D})\ \nexists\
\gamma=(u,...,v):\mathscr{L}(\gamma)=n+1$. Hence by Lemma 2 and 3, we can see
that between any pair of vertices following the direction of the $DAG$, we
have $\nexists\
\omega=(u,...,v):\mathfrak{L}(\omega)=n+1\because\mathfrak{D}_{{}_{dag}}(\mathcal{D})=n$.
Therefore, $n$ would be the index of
$A(\mathcal{D})\implies\beta(A(\mathcal{D})^{n})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$.
We know $n$ is the minimum such number since $\exists\
\omega=(u,...,v):\mathfrak{L}(\omega)=\mathfrak{D}_{{}_{dag}}(\mathcal{D})=n$
for some $u,v\in\mathbb{V}(\mathcal{D})$. ∎

###### Proof.

### $2\implies 1$

Assume $\exists\
k:\beta(A(\mathcal{D})^{k})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
where $k$ is the minimum such number to satisfy this property. Additionally,
assume that $\mathfrak{D}_{{}_{dag}}(\mathcal{D})=n$ where $k\neq n$. By
$1\implies 2$ we know that since
$\beta(A(\mathcal{D})^{k})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
then $k>\mathfrak{D}_{{}_{dag}}(\mathcal{D})$. However, since $k$ is the
minimum such number, and $k\neq n$, the assumption is false. Thus, $k=n$ must
be true. ∎

######  Corollary 4.1.

Let $\mathcal{D}$ be a DAG, where $\gamma_{\mathfrak{D}_{{}_{dag}}}$ is the
longest path with $v_{i},v_{j}\in\gamma_{\mathfrak{D}_{{}_{dag}}}$

$\displaystyle\exists\
k\in\mathbb{Z}_{|\mathbb{V}(\mathcal{D})|+1}^{*}:(\beta(A(\mathcal{D})^{n})-\beta(A(\mathcal{D})^{n-1}))_{i,j}=1$
$\displaystyle\ \ \ \ \ \ \land\exists\
(\beta(A(\mathcal{D})^{n-1})-\beta(A(\mathcal{D})^{n-2}))_{i,k}=1:\\{v_{k},v_{j}\\}\in\mathbb{E}(\mathcal{D})\iff(v_{k},v_{j})\subseteq\gamma_{\mathfrak{D}_{{}_{dag}}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ :\partial(v_{i},v_{k})=n-1\land\partial(v_{i},v_{j})=n\
\forall\ n\in\mathbb{Z}_{\mathfrak{D}_{{}_{dag}}(\mathcal{D})+1}$

###### Proof.

Let $P_{d}(c)=\\{\gamma=(u,...,w)\ |\
\mathscr{L}(\gamma)\in\\{0,1,...,c\\}\\}:c\in\mathbb{N}$

$\displaystyle\text{Assume
}(\beta(A(\mathcal{D})^{n})-\beta(A(\mathcal{D})^{n-1}))_{i,j}=1\land(\beta(A(\mathcal{D})^{n-1})-\beta(A(\mathcal{D})^{n-2}))_{i,k}=1:(v_{k},v_{j})\in\mathbb{E}(\mathcal{D})$
$\displaystyle\text{By Lemma 2, }\forall\
\beta(A(\mathcal{D})^{n})_{i,j}=1,\exists\ \gamma=(v_{i},...,v_{j})\in
P_{d}(n)$ $\displaystyle\text{Likewise, }\forall\
\beta(A(\mathcal{D})^{n-1})_{p,q}=1,\exists\ \gamma=(v_{p},...,v_{q})\in
P_{d}(n-1)$ $\displaystyle\therefore\forall\
(\beta(A(\mathcal{D})^{n})-\beta(A(\mathcal{D})^{n-1}))_{i,j}=1,\exists\
\gamma_{i,j}=(v_{i},...,v_{j})\in P_{d}(n)\setminus
P_{d}(n-1):\mathscr{L}(\gamma_{i,j})=n=\partial(v_{i},v_{j})$
$\displaystyle\land\forall\
(\beta(A(\mathcal{D})^{n-1})-\beta(A(\mathcal{D})^{n-2}))_{i,k}=1,\exists\
\gamma_{i,k}=(v_{i},...,v_{k})\in P_{d}(n-1)\setminus
P_{d}(n-2):\mathscr{L}(\gamma_{i,k})=n-1=\partial(v_{i},v_{k})$
$\displaystyle\text{Since }(v_{k},v_{j})\in\mathbb{E}(\mathcal{D})\iff\exists\
\gamma_{i,k}\in P_{d}(n)\setminus P_{d}(n-1)\land\gamma_{i,j}\in
P_{d}(n-1)\setminus P_{d}(n-2):\gamma_{i,j}=\gamma_{i,k}\cup(v_{j})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\iff(v_{k},v_{j})\subseteq\gamma_{i,j}\subseteq\gamma_{\mathfrak{D}_{{}_{dag}}}$

∎

##  4 Tree Search Algorithms

Algorithm 2 Linear Diameter Search $\left[Tree\right]$

1:procedure $\mathfrak{D}$($\Gamma$)

2: for $i\leftarrow 1,...,|\mathbb{E}(\Gamma)|$ do

3: if $\beta(A(\Gamma)^{i})=\beta(A(\Gamma)^{i-2})$ then

4: $\textbf{return}\ i-1$

5: $\textbf{return}\ -1$

Algorithm 3 Logarithmic Diameter Search $\left[Tree\right]$

1:procedure $\mathfrak{D}$($\Gamma,\epsilon=1$)

2: for $i\leftarrow\alpha,\alpha^{2},\alpha^{3},...,|\mathbb{E}(\Gamma)|$ do

3: if $\beta(A(\Gamma)^{i})=\beta(A(\Gamma)^{i-2})$ then

4: while $\beta(A(\Gamma)^{i})=\beta(A(\Gamma)^{i-2})$ do

5: $j\leftarrow i$

6: $i\leftarrow\frac{i+\alpha^{\lceil log_{\alpha}(i)\rceil-1}}{2}$

7: while $i\neq j+1$ do

8: if $j-i\leq\epsilon$ then

9: $\textbf{return}\ (i,j)$

10: if $\beta(A(\Gamma)^{i})=\beta(A(\Gamma)^{i-2})$ then

11: $j\leftarrow\frac{i+j}{2}$

12: else

13: $i\leftarrow\frac{i+j}{2}$

14: $\textbf{return}\ i$

15: $\textbf{return}\ -1$

Algorithm 4 Binary Diameter Search $\left[Tree\right]$

1:procedure $\mathfrak{D}$($\Gamma,l=0,h=|\mathbb{E}(\Gamma)|,\epsilon=1$)

2: $m\leftarrow\lfloor\frac{l+h}{2}\rfloor$

3: if $h-l\leq\epsilon$ then

4: $\textbf{return}\ (l,h)$

5: if $l=h$ then

6: $\text{return }m$

7: if $\beta(A(\Gamma)^{m+1})=\beta(A(\Gamma)^{m-1})$ then

8: $\text{return }\mathfrak{D}(\Gamma,l,m)$

9: else

10: $\text{return }\mathfrak{D}(\Gamma,m,h)$

##  5 Uniform Block Graph Search Algorithms

Algorithm 5 Linear LP Search $\left[Uniform\ Block\ Graph\right]$

1:procedure $\mathscr{LP}$($\Gamma$)

2: for $i\leftarrow 0,...,|\mathbb{E}(\Gamma)|$ do

3: if $\beta(A(\Gamma)^{i})=J_{|\mathbb{V}(\Gamma)|}$ then

4: $\textbf{return}\ i\cdot(\omega(\Gamma)-1)$

5: $\textbf{return}\ -1$

Algorithm 6 Logarithmic LP Search $\left[Uniform\ Block\ Graph\right]$

1:procedure $\mathscr{LP}$($\Gamma,\epsilon=1$)

2: for $i\leftarrow\alpha,\alpha^{2},\alpha^{3},...,|\mathbb{E}(\Gamma)|$ do

3: if $\beta(A(\Gamma)^{i})=J_{|\mathbb{V}(\Gamma)|}$ then

4: while $\beta(A(\Gamma)^{i})=J_{|\mathbb{V}(\Gamma)|}$ do

5: $j\leftarrow i$

6: $i\leftarrow\frac{i+\alpha{}^{\lceil log_{\alpha}(i)\rceil-1}}{2}$

7: while $i\neq j+1$ do

8: if $j-i\leq\epsilon$ then

9: $\textbf{return}\ (i,j)$

10: if $\beta(A(\Gamma)^{i})=J_{|\mathbb{V}(\Gamma)|}$ then

11: $j\leftarrow\frac{i+j}{2}$

12: else

13: $i\leftarrow\frac{i+j}{2}$

14: $\textbf{return}\ i\cdot(\omega(\Gamma)-1)$

15: $\textbf{return}\ -1$

Algorithm 7 Binary LP Search $\left[Uniform\ Block\ Graph\right]$

1:procedure $\mathscr{LP}$($\Gamma,l=0,h=|\mathbb{E}(\Gamma)|,\epsilon=1$)

2: $m\leftarrow\lfloor\frac{l+h}{2}\rfloor$

3: if $h-l\leq\epsilon$ then

4: $\textbf{return}\ (l,h)$

5: if $l=h$ then

6: $\text{return }m\cdot(\omega(\Gamma)-1)$

7: if $\beta(A(\Gamma)^{m})=J_{|\mathbb{V}(\Gamma)|}$ then

8: $\text{return }\mathfrak{D}(\Gamma,l,m)$

9: else

10: $\text{return }\mathfrak{D}(\Gamma,m,h)$

The algorithm for Block Graphs follows directly by the equality given in
Theorem 3. Hence, omitted as it is derivable from Uniform Block Graph
Algorithms

##  6 Directed Acyclic Graph Search Algorithms

Algorithm 8 Linear Diameter Search $\left[Directed\ Acyclic\ Graph\right]$

1:procedure $\mathfrak{D}_{{}_{dag}}$($\mathcal{D}$)

2: for $i\leftarrow 0,...,|\mathbb{E}(\mathcal{D})|$ do

3: if
$\beta(A(\mathcal{D})^{i})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
then

4: $\textbf{return}\ i$

5: $\textbf{return}\ -1$

Algorithm 9 Logarithmic Diameter Search $\left[Directed\ Acyclic\
Graph\right]$

1:procedure $\mathfrak{D}_{{}_{dag}}$($\mathcal{D},\epsilon=1$)

2: for $i\leftarrow\alpha,\alpha^{2},\alpha^{3},...,|\mathbb{E}(\mathcal{D})|$
do

3: if
$\beta(A(\mathcal{D})^{i})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
then

4: while
$\beta(A(\mathcal{D})^{i})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
do

5: $j\leftarrow i$

6: $i\leftarrow\frac{i+\alpha^{\lceil log_{\alpha}(i)\rceil-1}}{2}$

7: while $i\neq j+1$ do

8: if $j-i\leq\epsilon$ then

9: $\textbf{return}\ (i,j)$

10: if
$\beta(A(\mathcal{D})^{i})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
then

11: $j\leftarrow\frac{i+j}{2}$

12: else

13: $i\leftarrow\frac{i+j}{2}$

14: $\textbf{return}\ i$

15: $\textbf{return}\ -1$

Algorithm 10 Binary Diameter Search $\left[Directed\ Acyclic\ Graph\right]$

1:procedure
$\mathfrak{D}_{{}_{dag}}$($\mathcal{D},l=0,h=|\mathbb{E}(\mathcal{D})|,\epsilon=1$)

2: $m\leftarrow\lfloor\frac{l+h}{2}\rfloor$

3: if $h-l\leq\epsilon$ then

4: $\textbf{return}\ (l,h)$

5: if $l=h$ then

6: $\text{return }m$

7: if
$\beta(A(\mathcal{D})^{m})=\left[\mathbf{0}\right]_{|\mathbb{V}(\mathcal{D})|}$
then

8: $\text{return }\mathfrak{D}_{{}_{dag}}(\mathcal{D},l,m)$

9: else

10: $\text{return }\mathfrak{D}_{{}_{dag}}(\mathcal{D},m,h)$

##  7 Path Generating Algorithms

Algorithm 11 Generate $\gamma_{\mathfrak{D}}$ $\left[Tree\right]$

1:procedure $Generate\\_\mathfrak{D}$($\Gamma$)

2: $\gamma\leftarrow\left[\gamma_{1},\gamma_{2},...\right];t\leftarrow 0$

3: for $i\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

4: for $j\leftarrow i+1,...,|\mathbb{V}(\Gamma)|$ do

5: if
$(\beta(A(\Gamma)^{\mathfrak{D}(\Gamma)})-\beta(A(\Gamma))^{\mathfrak{D}(\Gamma)-2})_{i,j}=1$
then

6: $s\leftarrow i;d\leftarrow j;n\leftarrow\mathfrak{D}(\Gamma)-1;t\leftarrow
t+1$

7: $\gamma_{t}\leftarrow(v_{j})$

8: while
$n>1\land(\beta(A(\Gamma)^{n})-\beta(A(\Gamma))^{n-2})_{s,k}=1\land\\{v_{k},v_{d}\\}\in\mathbb{E}(\Gamma)$
do

9: $\gamma_{t}\leftarrow(v_{k})\cup\gamma_{t}$

10: $k\leftarrow d;n\leftarrow n-1$

11: $\textbf{return }\gamma$

Algorithm 12 Generate $\gamma_{l}^{max}$ $\left[(Uniform)\ Block\
Graph\right]$

1:procedure $Generate\\_\mathscr{LP}$($\Gamma$)

2: $\gamma\leftarrow\left[\gamma_{1},\gamma_{2},...\right];t\leftarrow 0$

3: for $i\leftarrow 1,...,|\mathbb{V}(\Gamma)|$ do

4: for $j\leftarrow i+1,...,|\mathbb{V}(\Gamma)|$ do

5: if
$(\beta(A(\Gamma)^{\mathscr{LP}(\Gamma)})-\beta(A(\Gamma))^{\mathscr{LP}(\Gamma)-1})_{i,j}=1$
then

6: $s\leftarrow i;d\leftarrow j;n\leftarrow\mathscr{LP}(\Gamma)-1;t\leftarrow
t+1$

7: $\gamma_{t}\leftarrow(v_{j})$

8: while
$n>0\land(\beta(A(\Gamma)^{n})-\beta(A(\Gamma)^{n-1}))_{s,k}=1\land\\{v_{k},v_{d}\\}\in\mathbb{E}(\Gamma)$
do

9: $\gamma_{t}\leftarrow(v_{k})\cup\gamma_{t}$

10: $k\leftarrow d;n\leftarrow n-1$

11: $\textbf{return }\gamma$

Algorithm 13 Generate $\gamma_{\mathfrak{D}_{{}_{dag}}}\left[Directed\
Acyclic\ Graph\right]$

1:procedure $Generate\\_\mathfrak{D}_{{}_{dag}}$($\mathcal{D}$)

2: $\gamma\leftarrow\left[\gamma_{1},\gamma_{2},...\right];t\leftarrow 0$

3: for $i\leftarrow 1,...,|\mathbb{V}(\mathcal{D})|$ do

4: for $j\leftarrow 1,...,|\mathbb{V}(\mathcal{D})|$ do

5: if
$(\beta(A(\mathcal{D})^{\mathfrak{D}_{{}_{dag}}(\mathcal{D})})-\beta(A(\mathcal{D}))^{\mathfrak{D}_{{}_{dag}}(\mathcal{D})-1})_{i,j}=1$
then

6: $s\leftarrow i;d\leftarrow
j;n\leftarrow\mathfrak{D}_{{}_{dag}}(\mathcal{D})-1;t\leftarrow t+1$

7: $\gamma_{t}\leftarrow(v_{j})$

8: while
$n>0\land(\beta(A(\mathcal{D})^{n})-\beta(A(\mathcal{D})^{n-1}))_{s,k}=1\land\\{v_{k},v_{d}\\}\in\mathbb{E}(\mathcal{D})$
do

9: $\gamma_{t}\leftarrow(v_{k})\cup\gamma_{t}$

10: $k\leftarrow d;n\leftarrow n-1$

11: $\textbf{return }\gamma$

##  8 Complexity Analysis

Define the order of concern to be,
$n:=|\mathbb{V}(\Gamma)|,m:=|\mathbb{E}(\Gamma)|$, and $\delta$ to be a small
value that depends on the number of bytes of an integer. Additionally, note
that for Trees and $DAG$’s,
$\mathfrak{D}_{{}_{dag}}(\Gamma)=\mathfrak{D}(\Gamma)=\mathscr{L}(\gamma_{l}^{max})=\mathscr{LP}(\Gamma)$.
Therefore the results shown below apply to the algorithms provided above.

######  Corollary 4.2.

The asymptotic complexity of Algorithm 1 (Booleanization)

$\beta(A(\Gamma_{1})\times A(\Gamma_{2}))\in\Theta(\delta n^{2})$

###### Proof.

$\beta(A(\Gamma_{1})\times
A(\Gamma_{2}))\in\Theta\left(\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=1}^{|\mathbb{V}(\Gamma)|}\sum_{k=1}^{\delta}1+\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=1}^{|\mathbb{V}(\Gamma)|}1\right)=\Theta(\delta
n^{2}+n^{2})=\Theta(\delta n^{2})$

∎

######  Corollary 4.3.

The asymptotic complexity of Algorithm 2, 5, and 8 (Linear Search)

$\mathfrak{D},\mathscr{LP}\in\Theta\left(\delta n^{2}\cdot m\right)$

###### Proof.

$\displaystyle\mathfrak{D},\mathscr{LP}\in\Theta\left(\sum_{i=1}^{|\mathscr{LP}(\Gamma)|}\delta|\mathbb{V}(\Gamma)|^{2}\right)=\Theta\left(\delta|\mathbb{V}(\Gamma)|^{2}\cdot|\mathscr{LP}(\Gamma)|\right)=\Theta\left(\delta
n^{2}\cdot m\right)$

∎

######  Corollary 4.4.

The asymptotic complexity of Algorithm 3, 6, and 9 (Logarithmic Search)

$\mathfrak{D},\mathscr{LP}\in\Theta\left(\delta n^{2}\cdot
log_{\alpha}(m)\right)$

###### Proof.

The search uses sequential power iterations over the matrix exponent variable,
$\alpha$. If $\alpha=2$ then $i\in\\{2,4,8,16,...,|\mathbb{E}(\Gamma)|\\}$.
Thus, following the sequence with a logarithmic cardinality factor up until
$i>\mathfrak{D}(\Gamma)$ which then performs a Binary Search on the values
between $\alpha^{\lceil
log_{\alpha}(\mathfrak{D}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathfrak{D}(\Gamma))\rceil-1}$ yielding the following complexity

$\mathfrak{D},\mathscr{LP}\in\Theta\left(\delta n^{2}\left(\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil+\lceil log_{2}\left(\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}\right)\rceil\right)\right)$
$\implies\mathfrak{D},\mathscr{LP}\in\Theta\left(\delta n^{2}\cdot
log_{\alpha}(m)\right)$

∎

######  Corollary 4.5.

Let $\epsilon$ denote the error range of where $\mathscr{LP}(\Gamma)$ lies.
Then we can see when $i>\mathscr{LP}(\Gamma)$ and $k$ steps of the Binary
Search section in Algorithm 3, 6, and 9 (Logarithmic Search) then

$\epsilon=\frac{1}{2^{k}}\left(\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}\right)$

###### Proof.

Once $i>\mathscr{LP}(\Gamma)$, we can see that $i=\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}$ and $j=\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}$. Furthermore, we enter the Binary
Search section of the Logarithmic Search algorithm only once
$i>\mathscr{LP}(\Gamma)$. Therefore, for every step $k$ in the Binary Search
section, we reduce the size of $j-i$ by half. Hence we have

$\epsilon=\frac{1}{2^{k}}\left(\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}\right)$

Which implies that for a given $\epsilon$ error bound, we can find the number
of steps in Binary Search with

$k=\lceil log_{2}\left(\frac{\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}}{\epsilon}\right)\rceil$

∎

######  Corollary 4.6.

The asymptotic complexity of Algorithm 4, 7, and 10 (Binary Search)

$\mathfrak{D},\mathscr{LP}\in\Theta(\delta n^{2}\cdot log_{2}(m))$

###### Proof.

The search starts at $\frac{|\mathbb{E}(\Gamma)|}{2}$ continuing as a standard
Binary Search algorithm with an allocated condition. Thus, using Corollary
4.5’s Binary Search section of Logarithmic Search, then we have $k=\lceil
log_{2}\left(\frac{\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}}{\epsilon}\right)\rceil$ where
$\epsilon=1$, $\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil}-\alpha^{\lceil
log_{\alpha}(\mathscr{LP}(\Gamma))\rceil-1}=|\mathbb{E}(\Gamma)|$ then
$k=\lceil log_{2}\left(|\mathbb{E}(\Gamma)|\right)\rceil$

$\displaystyle\implies\mathfrak{D},\mathscr{LP}\in\Theta\left(\delta
n^{2}\cdot k\right)=\Theta\left(\delta n^{2}\cdot
log_{2}(|\mathbb{E}(\Gamma)|)\right)=\Theta\left(\delta n^{2}\cdot
log_{2}(m)\right)$

∎

Note that running Algorithm 3, 4, 6, 7, 9, and 10 by default achieves the
exact value of the length of the longest path if $\epsilon=1$. However, if an
error bound is desired without the requirement of an exact value, then
Corollary 4.5 will provide expected bounds and error values.

######  Corollary 4.7.

The asymptotic complexity of Algorithm 11, 12, and 13

$Generate\\_\mathfrak{D},Generate\\_\mathscr{LP}\in\Theta\left(\delta
n^{2}\cdot m\right)$

###### Proof.

$Generate\\_\mathfrak{D},Generate\\_\mathscr{LP}\in\Theta\left(\sum_{i=1}^{|\mathbb{V}(\Gamma)|}\sum_{j=i+1}^{|\mathbb{V}(\Gamma)|}\sum_{k=1}^{|\mathscr{LP}(\Gamma)|}1\right)=\Theta\left(\delta|\mathbb{V}(\Gamma)|^{2}\cdot|\mathscr{LP}(\Gamma)|\right)=\Theta\left(\delta
n^{2}\cdot m\right)$

∎

##  9 Concluding Remarks

The algebraic approach presents itself as a promising method of efficiently
solving LPP on classes of graphs for which a polynomial solution does not
exist yet. In general, algebraic algorithms are guaranteed to be correct given
a proof of the algebraic condition it is based on. Hence, by defining
operations which are computable in efficient time, any polynomial sequence of
operations converging to the final algebraic condition would be guaranteed to
solve the problem in efficient time. While not as critical as time complexity,
given that a simple matrix datastructure is used to model the algebraic
objects, space complexity is also in polynomial order. Besides, unlike other
methods to solve LPP, the algebraic operations lead to new methods to
generating the longest path itself. Not only a single longest path, nor only
every path of the longest length, but also any path of any length. Therefore,
suggesting the ability to not only solve HPP in polynomial time for a class of
graphs, but also generate the specific hamiltonian path to traverse the graph.

Acknowledgements. I would like to express my immense gratitude to Dr. Ayman
Badawi for valuable discussion, consultation, and deliberation through my
discoveries.

## References

  * [1] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer Science & Business Media, 2003.
  * [2] R. W. Bulterman, F. W. van der Sommen, G. Zwaan, T. Verhoeff, A. J. M. van Gasteren, and W. H. J. Feijen, ”On computing a longest path in a tree,” Information Processing Letters, vol. 81, no. 2, pp. 93-96, Jan. 2002, doi: https://doi.org/10.1016/S0020-0190(01)00198-3.
  * [3] R. Uehara and Y. Uno, ”Efficient Algorithms for the Longest Path Problem,” Algorithms and Computation pp. 871-883, Jan. 2004, doi: https://doi.org/10.1007/978-3-540-30551-4_74.
  * [4] K. Ioannidou and S. D. Nikolopoulos, ”The Longest Path Problem is Polynomial on Cocomparability Graphs,” Algorithmica, vol. 65, no. 1, pp. 177-205, Oct. 2011, doi: https://doi.org/10.1007/s00453-011-9583-5.
  * [5] K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, “The Longest Path Problem Is Polynomial on Interval Graphs,” Mathematical Foundations of Computer Science pp. 403–414, Jan. 2009, doi: https://doi.org/10.1007/978-3-642-03816-7_35.
  * [6] Y.-L. Guo, C.-W. Ho, and M.-T. Ko, ”The Longest Path Problem on Distance-Hereditary Graphs,” Advances in Intelligent Systems and Applications vol. 1, pp. 69-77, Jan. 2013, doi: https://doi.org/10.1007/978-3-642-35452-6_9.
  * [7] R. Duan, H. Wu, and R. Zhou, ”Faster Matrix Multiplication via Asymmetric Hashing” arXiv.org Apr. 05, 2023. https://arxiv.org/abs/2210.10173