4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – j_random_hacker Feb 26 '18 at 16:30
  • $\begingroup$ I'm sorry but i don't understand. $\endgroup$ – Theta Feb 26 '18 at 16:39
  • $\begingroup$ 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? $\endgroup$ – j_random_hacker Feb 26 '18 at 16:41
  • $\begingroup$ 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? $\endgroup$ – Theta Feb 26 '18 at 16:44
  • $\begingroup$ 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. :/ $\endgroup$ – Theta Feb 26 '18 at 17:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Theta Feb 27 '18 at 11:25
  • $\begingroup$ 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. $\endgroup$ – Theta Feb 27 '18 at 12:04
  • $\begingroup$ Still cannot think something helpful. Can i have one more hint, please? Thank you. $\endgroup$ – Theta Feb 28 '18 at 10:08
  • $\begingroup$ @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.). $\endgroup$ – D.W. Feb 28 '18 at 12:16
  • $\begingroup$ 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. $\endgroup$ – Theta Feb 28 '18 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.