The Longest Path Problem is a question of finding the maximum length between pairs of vertices of a finite graph. In the general case, the problem is -hard. However, there is a subcollection of graph classes for which there exists an efficient solution. I will display my method which provides algorithms that are proven correct by their underlying algebraic operations unlike existing purely algorithmic solutions to this problem. We 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 exact conditions and associated polynomial-time algorithms. I will then show an algebraic construction with elements as graphs and two operations that have further underlying structure within them. Then, showcasing some results and theorems that exist behind the hidden structure of this algebraic construction.
An Algebra of Graphs and the Longest Path Problem