Hey everyone,
I recently learned about basic graph theory (BFS/DFS), and I would like to know approaches to the following two problems. I will discuss my thoughts after I present the problems.
1) Given an undirected graph $$$G = (V, E)$$$ whose $$$V$$$ vertices are colored with at most $$$V$$$ distinct colors, how can I determine whether there exist two vertices $$$u$$$ and $$$v$$$ with $$$d(u, v) \leq 2$$$ such that the color of $$$u$$$ is equal to the color of $$$v$$$?
This problem seems really similar to the bipartite coloring problem, but the key differences are that we're allowed to use up to $$$n$$$ colors, and we need to make sure that no two vertices have the same color within a distance of two. I thought about this problem for a while, and I couldn't come up with too much. I thought about somehow "augmenting" each node with the colors of its adjacent vertices, but I couldn't really get much from there. I'm not sure if this is the right direction or not.
2) Given a DAG $$$G = (V, E)$$$ with each vertex colored with colors $$$1$$$, $$$2$$$, or $$$3$$$, how can I find the set of all vertices colored $$$1$$$ that are reachable from both a vertex with color $$$2$$$ AND a vertex with color $$$3$$$?
So when I see DAG, I usually think of topological sort. But I really can't get anywhere with this problem. I thought about reversing the edges and performing a depth-first search from each of the vertices colored $$$1$$$, but this would be $$$O(V(V + E))$$$ in the worst case, and I'm pretty sure we can do better.
Could someone please help me with these graph theory problems? Thank you
1) If $$$d(u, v) == 1$$$ then it means there's an edge connecting two vertices of the same color, easy to check.
If $$$d(u, v) == 2$$$ then there is vertex $$$x$$$ such that $$$d(u, x) = 1$$$ and $$$d(x, v) = 1$$$. This vertex $$$x$$$ has two neighbors of the same color. You can iterate over all neighbors for each vertex $$$x$$$ and count how many times each color appears.
2) For each vertex $$$v$$$ define array $$$reachable[c][v]$$$, which denotes if vertex $$$v$$$ is reachable from another vertex of color $$$c$$$. Perform topological sorting. Assume we're processing vertex $$$x$$$. Then $$$reachable[color[x]][x] = true$$$. For $$$c$$$ different from $$$color[x]$$$ we have $$$reachable[c][x] = true <=>$$$ there exists an edge $$$(u, x)$$$ and $$$reachable[c][u] = true$$$.
This is very clever. Thank you.