CODEWITHSUNDEEP
pathgraph-theorycomplexity-theorydirected-graph
Manuel Eberl
Manuel Eberl

Reputation: 8278

Find length of longest trail in directed unweighted graph

I have a directed, unweighted, possibly cyclic graph that can contain loops and multiple duplicate edges (i.e. two edges from node 1 to node 2).

I would now like to find the length of the longest trail in this graph, i.e. the longest path that: - uses no edge twice (but if there are multiple edges from node 1 to node 2, it can use every one of them) - possibly visits nodes several time (i.e. it does not have to be a simple path)

In particular, is this problem NP-hard? I know that the longest simple path is NP-hard (reducing Hamiltonian Path to it) and the longest trail with edge reusal is in P (Bellman ford with weight -1 on every edge). However, with this problem, I am not quite sure and I could not find good information on it.

Upvotes: 2

Views: 827

Answers (1)

Ege Şencan
Ege Şencan

Reputation: 53

Although I am not completely sure, I think that this problem is NP-hard. As I understand, your question arises due to multiple edges between nodes. The graphs that has multiple edges between same nodes can be expanded to larger graphs with no multiple edges between them. Thus, a graph with multiple edges between same nodes has no difference than a graph without multiple edges.

Let me walk through a simple example to explain: Let there be a graph with 3 nodes (A,B,C) and 5 edges between them (A to B, A to B, B to A, B to C, C to A) This graph can be expanded and shown with 5 nodes and 7 edges. Lets expand the node A to 3 different nodes (A1, A2, A3). When we adjust the edges according to previous edges, there exists 7 edges(A1 to B, A2 to B, B to A3, B to C, C to A1, C to A2, C to A3) As a result, now we have a graph without multiple edges and can be evaluated with the help of Hamiltonian and Bellman Ford.

Upvotes: 1

Related Questions