CODEWITHSUNDEEP
graphcyclelongest-path
Diaz
Diaz

Reputation: 25

Longest path in unweighted undirected graph starting and finishing in the same vertex

I have a problem in which I need to find the longest path. Given an unveighted undirected graph. Starting from a given vertex I need to visit as many vertices as possible and finish in the same one without visiting each of them more then once.

Most of the algorithms I found were for a special case (acyclic, directed etc.). An idea can be to find Hamiltonian cycle for every subset of the vertices (the subset can be generated with backtrack). But I guess there must be a far better algorithm.

Upvotes: 2

Views: 396

Answers (1)

iacob
iacob

Reputation: 24371

As you've discovered, finding the largest cycle involves finding the Hamiltonian cycles of its subgraphs, and thus is NP-complete - unless you're working on some special class of graphs, any solution is going to be exponential in complexity.

A smart brute force approach (e.g. bitmask) is the best efficiency one can get for this type of problem.

Upvotes: 1

Related Questions