typedeftemplate's blog

Graph theory problem
By typedeftemplate, history, 4 years ago, In English

Hi everyone,

I've been learning a lot of graph theory lately, and I've come across the following question, which I am having trouble with:

Suppose you are given a directed acyclic graph $$$G = (V, E)$$$ in which each vertex is colored one of two colors. You are also given two vertices $$$u$$$ and $$$v$$$ in the graph. How can I determine whether there is a path from $$$u$$$ to $$$v$$$ consisting of only one color (each intermediate vertex other than $$$u$$$ and $$$v$$$ are required to have the same color, the colors of $$$u$$$ and $$$v$$$) don't matter.

I thought about applying topological sort since it's a DAG, but then I don't really know how to proceed. Can someone please help me?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you share the link to the problem? I want to check if my solution is correct or not. Anyways maybe we can run dfs from the start and while calling for next calls we should also check the colors of the to node and from node?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For single query u,v u can simply use DFS keep 2 counts distance of v from u and no. Of say red nodes upto v take u as node If u wanna handle multiple queries u can use lca algorithms calc same things distance between u and v and no. Of red coloured nodes between u and v

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Fix the color you want. Then just run a dfs starting from $$$u$$$ that only allows traversing vertices of that color, and see if you can ever reach $$$v$$$. There are only 2 colors, so this is $$$O(V + E)$$$.

edit: Actually, this is $$$O(V + E)$$$ regardless of the number of colors, provided that you take care to not visit all neighbors of $$$u$$$ each time.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So, if there are several queries, you can add the inputted edge between two vertices only if they are of same colour. By this way, your graph should break into several connected components and for each query, you just need to check if the two vertices 'u' and 'v' are connected to at least one common connected component in the original graph.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The graph is directed, so being in the same component doesn't necessarily mean there's a path from $$$u$$$ to $$$v$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, you are right. I overlooked the directed part. Any efficient algorithm for answering queries then ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After we break into connected components, each connected component has only one colour in it so it's the same as normal reachability problem on a DAG. I do not know of any faster method than the one in this blog.

        → Reply