CODEWITHSUNDEEP
algorithmcomplexity-theorygraph-theorycomputation-theoryoperations-research
hola
hola

Reputation: 612

Approximating longest cycle in a directed graph

Finding the longest cycle (By cycle I mean cycle with no node repitition) in a directed graph is an NP-hard problem, otherwise we can tell if the graph is Hamiltonian or not. My question is: Is there any alpha-approxiamtion polynomial algorithm for this problem ?

Upvotes: 2

Views: 593

Answers (1)

m.raynal
m.raynal

Reputation: 3113

Since the longest directed path problem in a directed graph cannot be approximated in polynomial time within a factor of n^(1-epsilon) for any epsilon > 0, we can quickly deduce that it is also the case for the longest cycle in a directed graph unless P=NP (source).

You can make the reduction as follows:
Choose a vertex v, duplicate v into v1 and v2, duplicate all concerned arcs as well. Now find the longest directed path from v1 to v2.
Do that for all vertices in the graph. That gives you the longest directed cycle in the graph.

Conclusion: there is no alpha-approximation in polynomial time for the longest cycle problem in directed graphs (unless P=NP of course).

Upvotes: 2

Related Questions