Crthuky

Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and t, that you pass through as few red nodes as possible.

Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.

Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.

I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.

To solve this, you need to use $BFS$. But first, manipulate $G$ so that the path will always favor blue vertices.

The solution has 2 parts:

1. Use $DFS$ on blue vertices only, to find all all-blue strongly connected components, or $SCC$. Let's denote each $SCC$ by $v'$. Now, each blue $v in v'$ will be "compressed" to a single vertex $u$, and an edge $(u,x)$ will be added for every $x in N(v')$.
   Note any such $x$ is necessarily red.
   This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.

Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertice.

2. Use $BFS$ from $s$. That length of the path to $t$ will essentially be the shortest path under the constraint of least red vertices in the path.

Convert $G$ to a directed graph $G'$ where we have two edges $(u,v)$ and $(v,u)$ in $G'$ for every edge $u,v$ in $G$. Let the length of $(u,v)$ be 1 if $v$ is a red node and 0 otherwise. Now run Dijkstra's algorithm on $G'$ from the starting node $s$ to the ending node $t$.

It is clear that the shortest path thus found passes as few red nodes as possible.