-1

Consider a weighted directed graph, including V vertices and E edges. I am looking for an algorithm that finds the shortest cycle that passes through only S certain node (must pass through all nodes in S), not the other nodes. The cycle starts and ends from node w in set S.

Is it possible to delete the nodes in the set of V - S and also delete their corresponding connected edges, and then apply an algorithm (for finding the shortest cycle) to this graph, including only S nodes and their corresponding edges?

I emphasize that we only consider the nodes in set S, not the other nodes.

I am not sure if the below link is relevant to my question. The link asks for the shortest cycle that must pass through the blue nodes, but the cycle may pass through the black ones (I am not sure about this).

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

AmirHosein Adavoudi
  • 117
  • 6
  • 2
    I think your approach is reasonable. Just remove the edges that have at least one vertex not in S (if you have an adjacency list or edge list) or zero out the columns/rows of vertices not in S in the adjacency matrix. – beaker Jan 04 '23 at 16:48
  • @beaker: Do you mean that the question asked in the link is irrelevant to me? If yes, may I ask you which algorithm I can use for my question? Can I solve it in polynomial time? Could you please refer me to a solution? Thanks. – AmirHosein Adavoudi Jan 04 '23 at 16:53
  • 1
    See https://stackoverflow.com/questions/47491806/find-the-lowest-weight-cycle-in-a-weighted-directed-graph-using-dijkstras – beaker Jan 04 '23 at 16:58
  • @beaker: Thank you for your help. I am wondering why my question is considered duplicated in the below link while my question is different from the ones asked in the links! https://stackoverflow.com/questions/74976311/find-the-shortest-cycle-in-a-directed-graph-passing-through-certain-nodes – AmirHosein Adavoudi Jan 04 '23 at 17:00
  • 1
    Because you never mention (that I can see) that the path can go **only** through nodes of S. If you allow the path to go through other nodes, it's a different problem. – beaker Jan 04 '23 at 17:05
  • @beaker: Besides your reference, can I also use the below link for my current question? https://stackoverflow.com/questions/3911626/find-cycle-of-shortest-length-in-a-directed-graph-with-positive-weights – AmirHosein Adavoudi Jan 04 '23 at 17:05
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/250845/discussion-between-amirhosein-adavoudi-and-beaker). – AmirHosein Adavoudi Jan 04 '23 at 17:09
  • 1
    "Is it possible to delete the nodes in the set of V - S and also delete their corresponding connected edges, and then apply an algorithm (for finding the shortest cycle) to this graph?" Yes. – ravenspoint Jan 04 '23 at 21:11
  • 1
    Are you now saying that the cycle **must** pass through **all** vertices in **S** and **must not** pass through **any** vertices of **V - S**? This is very different from the question you asked above. – beaker Jan 05 '23 at 18:21
  • 1
    "not the other nodes" What does this mean? That visiting the unspecified nodes is forbidden? Or, you do not care if the unspecified nodes are visited or not? – ravenspoint Jan 05 '23 at 18:24

2 Answers2

1

Yes, the way your problem is stated, the consider approach is correct.

A graph where you remove all vertices that don't belong to a set S is called an induced subgraph. Every path/cycle in the original graph that only uses vertices from S can be found in the induced subgraph, too. Therefore, finding the shortest cycle in the induced subgraph is equivalent to finding the cycle in the original graph.

If your problem requires to find the shortest cycle that uses all nodes in S, then you're solving the travelling salesman problem, which is known to be NP-hard, which means there is no known (and likely no existing) polynomial algorithm. That said, it is a well studied problem, you can choose from both exact algorithms (if the set is small enough) and heuristics/approximations for larger scale.

voidengine
  • 2,504
  • 1
  • 17
  • 29
  • To voidengine: Thank you. The solution to my problem is similar to the traveling salesman problem (TSP)? I am not sure if I can solve this problem polynomially or not. Assume that the S= V; then it means finding the shortest cycle starting from and ending the node w and passing through all nodes, which, I think, is equivalent to the TSP problem. Am I right? – AmirHosein Adavoudi Jan 05 '23 at 08:03
  • 1
    That really depends on how you precisely specify the problem - does the cycle need to include ALL vertices from S, or just some? Also, are all the weights positive, or are there some negative ones? – voidengine Jan 05 '23 at 08:44
  • To voidengine: The cycle needs to include all vertices from S, and all the weights are positive. Regarding this, is it possible to solve this problem polynomially? – AmirHosein Adavoudi Jan 05 '23 at 09:22
  • 1
    @AmirHoseinAdavoudi in this case it is indeed reducible to TSP and cannot be solved polynomially – pasthec Jan 05 '23 at 16:13
  • 1
    No, in that case it boils down to solving TSP, which is NP-hard. I've updated the answer based on that added info – voidengine Jan 05 '23 at 23:52
  • @voidengine: May I ask you which version of TSP is suitable for a graph with a number of nodes between 2 and 7? The graphs are connected but not complete. – AmirHosein Adavoudi Jan 06 '23 at 07:42
  • 1
    With such a tiny problem size, you can basically use any exact algorithm, even a brute-force search that compares all possibilities should be very fast for such input – voidengine Jan 06 '23 at 22:09
1

The first step is to detect the cycles that are present in your graph, if any

This can be done by modifying a depth first search ( DFS ) as follows:

- run DFS 
    - IF a node is reached for the second time 
       - IF path exists from node reached again to current DFS node
          - the path is a cycle

Now you can filter the cycles detected for your criteria ( visit nodes in S, shortest, etc )

Here is the C++ code for a DFS that detects and records cycles

std::vector<std::vector<vertex_t>>
cGraph::dfs_cycle_finder(const std::string &start)
{
    std::vector<std::vector<vertex_t>> ret;

    // track visited vertices
    std::vector<bool> visited(vVertex.size(), false);

    // vertices waiting to be processed
    std::stack<vertex_t> wait;

    // start at the beginning
    wait.push(vVertex[index(start)]);

    // continue until no more vertices need processing
    while (!wait.empty())
    {
        vertex_t v = wait.top();
        wait.pop();
        int vi = index(v);
        if (!visited[vi])
        {
            visited[vi] = true;

            for (vertex_t w : adjacentOut(v))
            {
                if (!visited[index(w)])
                {
                    wait.push(w);
                }
                else
                {
                    // previously visited node, check for ancestor
                    auto cycle = path( w, v );
                    if( cycle.size() > 0 ) {
                        // found a cycle
                        cycle.push_back( w );
                        ret.push_back(cycle);
                    }
                }
            }
        }
    }
    return ret;
}

The complete application for this is at https://github.com/JamesBremner/graphCycler

Example output:

node a linked to b
node b linked to c
node c linked to d
node d linked to a

cycle: a b c d a
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • The above comments state that my problem is reduced to the TSP problem. Now, I am wondering if your DFS solution works for my TSP problem. I am looking for the shortest cycle passing through all nodes in S. Does your DFS algorithm finds such a cycle? Thank you for your help. – AmirHosein Adavoudi Jan 07 '23 at 07:55
  • I cannot tell because you have not described your TSP problem. If you have two different problems, you should ask two different questions. ( I would advise concentrating on one problem at a time ) – ravenspoint Jan 07 '23 at 13:41
  • 1
    Found some serious bugs in the cycle finder while doing unit testing. I have fixed them and updated my answer and the repository. – ravenspoint Jan 08 '23 at 17:13