Showing NP-completeness of longest path problem

  • Thread starter TaPaKaH
  • Start date
  • Tags
    Path
In summary, the problem of determining whether there exists a simple s,t-path in a directed graph G of length at least K is NP-complete. A reduction from directed Hamiltonian cycle can be used to prove this, as well as other NP-complete problems such as 2-partition, 3-partition, TSP (undirected), ILP, SAT, 3-SAT, clique, vertex cover, independent set, and Hamiltonian path and cycle.
  • #1
TaPaKaH
54
0

Homework Statement


Show that the following problem is NP-complete:
Given: A directed graph ##G=(V,E)##, source and target nodes ##s,t\in V## and a parameter K.
Goal: Determine whether there exists a simple ##s,t##-path in ##G## of length at least ##K##.

The Attempt at a Solution


I've already shown that the problem is in NP, but I can't come up with a poly time reduction from a known NP-complete problem. Any ideas welcome.
 
Physics news on Phys.org
  • #2
TaPaKaH said:

Homework Statement


Show that the following problem is NP-complete:
Given: A directed graph ##G=(V,E)##, source and target nodes ##s,t\in V## and a parameter K.
Goal: Determine whether there exists a simple ##s,t##-path in ##G## of length at least ##K##.

The Attempt at a Solution


I've already shown that the problem is in NP, but I can't come up with a poly time reduction from a known NP-complete problem. Any ideas welcome.

Google "longest path problem"; several on-line articles have all you need.
 
  • #3
TaPaKaH, what are some NP-complete problems you are allowed to reduce to? Ones that are graph related already (ones that are related to doing walks around a graph in particular) would be particularly nice as starting points.
 
  • #4
2-partition, 3-partition, TSP (undirected), ILP, SAT, 3-SAT, clique, vertex cover, independent set, Hamiltonian path (undirected) and cycle (directed and undirected) is what I am allowed to use.
 
  • #5
I just managed to come up with a reduction from directed Hamiltonial cycle.
 

Related to Showing NP-completeness of longest path problem

1. What is the definition of NP-completeness?

NP-completeness is a term used in computer science to describe a problem that is at least as difficult as the hardest problems in the complexity class NP (Non-deterministic Polynomial time). This means that if a problem can be solved in polynomial time, then all NP-complete problems can also be solved in polynomial time.

2. What is the longest path problem?

The longest path problem is a graph optimization problem that involves finding the longest simple path between two nodes in a graph. This means that the path cannot contain repeated nodes, and it must start and end at the specified nodes.

3. How is NP-completeness determined for a problem?

To show that a problem is NP-complete, it must first be shown to be in the class NP. This means that a solution to the problem can be verified in polynomial time. Then, a reduction from a known NP-complete problem must be shown, meaning that the known problem can be transformed into the new problem in polynomial time.

4. How is NP-completeness of the longest path problem proven?

To prove the NP-completeness of the longest path problem, it must first be shown that it is in the class NP. This can be done by providing a certificate, or a potential solution, and demonstrating that it can be verified in polynomial time. Then, a reduction from a known NP-complete problem, such as the Hamiltonian path problem, must be shown. This reduction will show that the Hamiltonian path problem can be transformed into the longest path problem in polynomial time.

5. What implications does showing NP-completeness of the longest path problem have?

Showing NP-completeness of the longest path problem means that it is one of the hardest problems in the class NP. This means that it is highly unlikely to have a polynomial time algorithm to solve it, and it is therefore considered to be intractable. This has implications for real-world applications, as it may be necessary to use approximation algorithms or heuristics to find solutions to this problem.

Similar threads

MHB Proving Longest Path Belongs to NP & Reducing Hamiltonian Path
    • Programming and Computer Science
Replies
19
Views
4K
NP-Complete Problem: Determine if NFAs A and B Accept Same Language
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
MHB Is HSC NP-Complete in Graph Theory?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Proof of NP-completeness via reduction
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
MHB Solving Decision Problem with k Colors - NP-Complete
    • Programming and Computer Science
Replies
6
Views
2K
MHB Is the Subgraph Isomorphism problem NP-complete?
    • Programming and Computer Science
Replies
1
Views
2K
MHB Ice Cream : NP-complete problem
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
MHB The traveling salesman problem is NP-complete
    • Programming and Computer Science
Replies
1
Views
2K
MHB Maximizing Independent Set in Graphs: Proving NP-Completeness
    • Programming and Computer Science
Replies
9
Views
3K

Hot Threads

Recent Insights

Back
Top