Overview

The longest path problem (LP) is to find a simple path of maximum length between two given vertices of a graph where length is defined as the number of edges or the total weight of the edges in the path. The problem is known to be NP-complete and has several applications such as designing circuit boards, project planning, information retrieval or patrolling algorithms for multiple robots in graphs.
We proposed an optimal algorithm for solving the longest path problem in undirected graphs. By using graph partitioning and dynamic programming, we designed an algorithm which is significantly faster than other state-of-the-art methods and can solve more instances. Here we provide the implementation of the algorithm as easy to use open source software.

A maze with a longest path.



News:
8th March 2017: Provided benchmark problems.
16th February 2017: Initial release.
14th February 2017: Published arXiv report. Link to PDF.

Licence

The program is licenced under GPL 3.0. Please let us know if you need a commercial licence.
If you publish results using our algorithms, please acknowledge our work by quoting the following paper (PDF):

@techreport{balyo2017,
             AUTHOR = {Balyo, Tomas and Fieger, Kai and Schulz, Christian},
             TITLE = {{Optimal Longest Paths by Dynamic Programming}},
             PUBLISHER = {Springer},
             JOURNAL = {Technical Report. arXiv:1702.04170},
             YEAR = {2017}
}

Download

Benchmark Graphs

We provide a benchmark with various instances for the longest path problem. The benchmark consists of two main categories ``mazes'' and ``others''. The instances we provide here are either in DIMACS format (mazes) or in the METIS format (others). Mazes have been generated using the maze generator provided in the KaLP framework using a different random seeds, side lengths of the mazes and amounts of blocked cells. The category ``others'' contains subgraphs of other publicly available graphs.

Support

  • Write us an email if you need support!
  • We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.
  • Graphs used in our papers will be provided to you on request!

Other Open Source Frameworks

  • KaHIP -- Karlsruhe High Quality Partitioning
  • ParHIP -- Parallel High Quality Partitioning
  • KaDraw -- Karlsruhe Graph Drawing
  • KaMIS -- Karlsruhe Maximum Independent Sets
  • VieM -- Vienna Mapping and Sparse Quadratic Assignment