1

A similar question of mine was asked in the below link, where one of the comments states that "The problem is certainly NP-hard because TSP can be reduced to it".

Finding shortest circuit in a graph that visits X nodes at least once

On the other hand, in another link shown below, one of the solutions says that by modifying Dijkstra's algorithm, the complexity would be $O(n^3)$.

Find cycle of shortest length in a directed graph with positive weights

I am wondering which solution in one of those links is correct.

AmirHosein Adavoudi
  • 117
  • 6

1 Answers1

1

From your description you only want to find any shortest cycle, so the second link applies to you and you can find an efficient algorithm. In the first case the question asked for the shortest cycle going through some set of vertices.

pasthec
  • 329
  • 1
  • 10
  • In the first link, I am wondering if it is possible to delete the nodes which are not blue and also delete their connected edges, which leads to a graph with only blue nodes, and then we apply the algorithm in the second link? – AmirHosein Adavoudi Jan 04 '23 at 14:04
  • @I doubt that your answer is correct. Based on your argument, we apply the algorithm in the second link on the graph defined in the first link and then obtain all possible shortest cycles. Then, among the cycles, we look for the one that passes through our desired nodes. Hence, this gives us a linear complexity. – AmirHosein Adavoudi Jan 04 '23 at 14:09
  • 1
    Not always, sometimes the shortest cycle might go through some nodes which are not blue (imagine all edges between blue nodes have very large weights and all edges between blue nodes and other nodes have very small weights, a shortest cycle would then alternate between blue nodes and non-blue nodes). – pasthec Jan 04 '23 at 14:10
  • 1
    For your second comment, the shortest cycle going through all blue nodes is not always the shortest cycle relative to any node. To see it picture a fully connected graph with all weights equal to 1 and all nodes are blue, the shortest cycle that goes through all blue nodes is of length the number of nodes + 1, whereas the shortest cycle respective to any single node is of length 2. – pasthec Jan 04 '23 at 14:14
  • Thank you for your helpful comments. Regarding the algorithm in the first link, is it possible to obtain all shortest cycles with K edges using Dijkstra (K is the number of edges needed to create a cycle with only blue nodes). Then among the cycles, we select the cycle that passes through our desired nodes (blue ones)? – AmirHosein Adavoudi Jan 04 '23 at 14:29
  • 1
    I don't get what you mean by all shortest cycles. If you mean shortest cycles going through one node, none of them might go through all blue nodes. On a side note the first link is right as it is NP-complete, so if you think you found an efficient solution to it, it is almost 100% sure it's incorrect. – pasthec Jan 04 '23 at 14:36
  • May I ask if you know an algorithm more efficient than that in the first link for finding the shortest cycle passing through the blue and zero nodes? – AmirHosein Adavoudi Jan 04 '23 at 14:38
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/250839/discussion-between-amirhosein-adavoudi-and-pasthec). – AmirHosein Adavoudi Jan 04 '23 at 14:44