The complexity of a variant algorithm for the Travelling Salesman Problem (TSP)

Question

What is the algorithm's complexity for a variant of the TSP problem where every node must be visited at least once, meaning that a node can be visited more than once? (The cycle starts from a specific node and, after passing all nodes (at least once) returns to the start node)

In the below link, I found a relevant algorithm, but its complexity is not given. https://stackoverflow.com/questions/75028657/find-the-shortest-cycle-in-a-positive-weighted-directed-graph-passing-through-on/75032146?noredirect=1#comment132525164_75032146

Answer 1

Assuming the algorithm from the mentioned stackoverflow post (presented without a proof of correctness)

* remove nodes and associated edges that are not in S
# a factor of N
* Loop N over nodes
   # A term O(N * log(N))
   * Construct a spanning tree for the graph starting at N
   # A term O(N)
   * Connect leaf nodes of spanning tree
   # A factor of N
   * LOOP P over leaves of spanning tree
        * Mark P visited
        * set v = P
        # Here every iteration at one node is visited
        # so Another factor of N
        * While nodes remain unvisited
            * Set w to connected unvisited node nearest to v
            * IF w does not exist 
                # Without precomputation, this gives another O(N) term
                * Set w to nearest reachable node on spanning tree
                * Increment visits to nodes on path between v and W, excluding v and w
            * Mark w visited
            * Set v to w
        * Set L to length of path found
        * IF L < bestL
           * Set bestL = L
           * Set bestPath to current path
        * IF bestL == number of nodes - 1 break out of all loops
# O(N) term
* Find shortest path from end of bestPath back to beginning

Taking into account the operations commented on the algorithm the complexity is $O(N^2 log(N) + N + N^4)$ that can be simplified as $O(N^4)$.

A correct algorithm

An algorithm easy to prove correct is

# A O(N^3) term
* Construct a graph G' with so that every pair u,v 
* is connected by a edge of cost equal to the best 
* path between u,v, in G
# A N! term
* Solve the TSP on G'

And has complexity $O(N^3 + N!)$, this makes me suspicious about the previous algorithm, is it providing a faster algorithm for TSP problem on fully connected graphs?

Proof

By construction, if G' has an edge (u,v), the shortest path in G is the cost of the edge (u,v). If w is in the shortest path connecting u to v, G' also have edges (u,w) and (w,v).

So G' gives a way to hide the complexity of shortcuts.

The minimum cost trip G' is $u_0, u_1, \ldots, u_N$, has the minimum cost achievable for a trip passing through $u_0, u_1, \ldots, u_N$ in G. The solution the TSP G' is the minimum cost trip considering all the permutations of the vertices. Any trip visiting all the vertices of G' will have cost higher than at least one subsequence that gives the permutation of all the vertices of G. It follows that the minimum achievable cost of a trip visiting all the vertices in G is the cost of the optimal TSP solution in G'.