Search code examples
algorithmgraphpath-findingnp

simple path in Graph with special nodes with max amount of special nodes

I have this problem: Given a graph G = (V,E), that has a subset of the nodes called, R, that are "special" nodes. The amount of special nodes can very from case to case. The graph can be directed, undirected, does not have weights, and can contain cycles.

Now, I need a algorithm that can find a path from a node s to a node t, that passes through a maximum amount of the "special" nodes in R.

Im aware that this problem is np-hard, and is easily reducible from hamiltionian path, but I i've been looking for different ways of solving it without having to bruteforce all paths.

First attempt

First I tried doing some preprocessing of the graph, where every edge that goes to a "normal" node, gets a weight of 2, and every edge to a node in R gets a weight of 0. Then I would just run dijkstra on the graph.

A counterexample this could however look like this:

enter image description here

In this graph, dijkstra would pick path [s,4,t] even though path [s,1,2,3,t] is a actual simple path with the maximum amount of red nodes

Second Attempt

My second attempt was a bit more convoluted. In this attempt I would run a bfs from the s-node and each R-node in the graph. I would then createa a new reachabilitygraph that could model which R-nodes that are connected to each other.

This approach would run into major issues in any graph that has cycles or is not directed, as connections between R-nodes that did not exist in the original graph would be included in the new graph.

So if anyone has any bids on any smart preprocessing steps that I could take, I would be cery happy

Solution

  • Your first method seems good, for example:

    • weigh of all edges to some node v in R = 1
    • weigh of rest of edges = 0

    Then run Dijkstra with a cutoff = max special nodes