Book of programming problems

Complexity (1-100): 30

A graph with equal edge lengths is given. Find the longest path in that graph such that it does not contain any vertex twice.

The graph is specified by a connectivity matrix M, where M_i,j is 1 if if there is an edge between vertexes i and j, and 0 otherwise. The matrix is symmetric: M^T=M. The input file contains the number of vertexes N. The following N lines contain matrix data, N numbers at each row. These are some self-tests:

1. 13 vertex graph. The longest path: 1 8 7 6 5 2 3 4 9 10 11 13 12
2. A full graph with 12 vertexes. The longest path is any permutation of vertexes, e.g. 1 2 3 4 5 6 7 8 9 10 11 12
3. 11 vertex, 15 edges graph.The longest path is 6 7 1 5 2 3 4 8 9 10 11
4. A full graph with 8 vertexes. The longest path is any permutation of vertexes, e.g. 1 2 3 4 5 6 7 8

We start with a subproblem: find a longest path Path(s) in a graph G starting from a vertex s. Then we can solve the subproblem for all graph vertexes and find the longest path. A simple backtracking algorithm would remove the vertex s and solve the subproblem for vertexes adjacent to s: Path(s'₁), Path(s'₂), ..., Path(s'_n).

We can reduce the number of combinations by analysis of graph partitioning by removing a vertex. If  after vertex removal we get a set of connective components (which are maximum connective subgraphs), then estimate the length of the solution in each of components (the length cannot exceed the number of vertexes in a component - 1) and remove from consideration components that will never produce a path longer then the longest path found so far.