# Given an oriented graph, return true if paths have a specified length

I'm having trouble solving this exercise about graphs, I hope you can help me:

Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an integer $k$, verify in $O(|V|+|E|)$ if each path that starts from a vertex $v \in A$ and connect a vertex $u \in B$ have a length that is greater or equal than $k$.

So if each vertex in $A$ that connect a vertex in $B$ have a length that is greater or equat to $k$, you should return $true$; otherwise, if exists at least one vertex of $A$ that connect a vertex in $B$ on a path that have a length that is less than $k$, you should return $false$.

My problem is to guarantee the linearity on the graph's dimension. My idea was to execute $|A|$ BFSs, one for each node that is contained in $A$. But, if $|A|=|V|$ i have a complexity that's squared on the graph's dimension.

Thank you very much.

New Update : I've tried to think about the Dijkstra algorithm; in that algorithm i have one source and i have to calculate the shortest path from the source and other nodes. Still it's easy if i have one source, but if i have a set of nodes, still cannot guarantee the linearity. Please, do you have more specific hint?

• Hint: Imagine if there was an extra vertex that was connected to some of the vertices. Can you find a relationship between distances from this vertex, and distances from its neighbours? – j_random_hacker Feb 26 '18 at 16:30
• I'm sorry but i don't understand. – Theta Feb 26 '18 at 16:39
• It's tough to give a stronger hint without "giving the game away"... Another way to approach it would be: Can you somehow combine those BFSes in a way that is still useful? – j_random_hacker Feb 26 '18 at 16:41
• Maybe if during a BFS i find more than one vertex that's in A, i will not execute a BFS on that vertices. What do you think? – Theta Feb 26 '18 at 16:44
• No it can't work, because during a BFS i will just check distances between the source from each B vertex, so if i find another A vertex i will not check the distance between this and the other Bs. So still i don't know how to work with that. :/ – Theta Feb 26 '18 at 17:49

Let's say a vertex $v$ is at distance $t$ from the set $A$ if there exists a path of length $t$ from some element of $A$ to $v$; and there is no shorter path.

Can you think of an efficient way to compute the distance from $A$ to each individual vertex in the graph?

Perhaps you might like to modify BFS. Hint:

Maybe you can think of some way to change the initialization, to make BFS do what you want.

• If i have just $v$ to check, i can transpose the graph and start the BFS using $v$ as a source. But still cannot solve the problem if i have a set of nodes, because that set can have the same size of $V$. – Theta Feb 27 '18 at 11:25
• If i hadn't the constraint about the complaxity, it would have been easy: my idea was to start a BFS for each node inside the set $A$ and compute the distance from the current source in $A$ and the other nodes. If during the visit i find a vertex that's in $B$ and have a distance that's less than $k$, i stop and return $false$; otherwise, i continue the algorithm. Still can't figure it out how i can reduce the complexity. – Theta Feb 27 '18 at 12:04
• Still cannot think something helpful. Can i have one more hint, please? Thank you. – Theta Feb 28 '18 at 10:08
• @Theta, take another look at my hint. I mentioned something about changing the initialization. Try thinking about that, rather than making other changes to BFS (e.g., no reversing the graph, etc.). – D.W. Feb 28 '18 at 12:16
• During an initialization in a BFS: i color the source vertex as grey, say that the distance to him is 0 and i add the vertex in the queue. Do you mean that initialization? Or do you mean anything else? Thanks. – Theta Feb 28 '18 at 14:22