An Algebraic Approach to the Longest Path Problem

Autor:	Khazali, Omar Al
Rok vydání:	2023
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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 NP-complete. 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. Despite this, we propose a new method of approaching the longest path problem with exact algebraic solutions that give rise to polynomial-time algorithms. Our method 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. In addition, we display additional algorithms that can generate every possible longest path of acyclic graphs in efficient time, as well as for block graphs. Comment: Revised after reviewer comments
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2312.11469 Zobrazit plný text záznamu View this record from Arxiv