1
$\begingroup$

Let $D=(V,E)$ a directed graph.

How to color nodes of $D$ in white and black such that:

  1. No two white colors are adjacent, and
  2. For each black node there exists at least one white node which is adjacent to it or between some white node and the black node there exists one directed path of length at most $2$.

It can be done using $DFS$, but how to start? It sound like bipartite/tripartite directed graphs..

$\endgroup$
0
$\begingroup$

This problem is equivalent to finding a maximal independent set and colouring it white. To solve it, depth-first search on the graph, and colour the source node white.

If the graph is directed, change it to an undirected graph by replacing every edge with an undirected edge.

To clarify the terminology, "no two white colors are adjacent" means if 2 white vertices are connected by a directed edge, it violates this condition, so here the edge behaves as it is undirected. Since "between the white node and the black node there exists one directed path of length at most 2", so if there is an edge from the white node to the black node, it satisfies this criteria. Since "for each black node there exist at least one white node which is adjacent to it", if there is an edge from the black node to the white node, this criteria is also satisfied.

Let $x$ be the current node in the depth-first search.

If any of $x$'s neighbours has been coloured white, colour $x$ black. Otherwise, colour $x$ white.

Checking $x$'s neighbours can be done in $O(E)$ time for the entire graph over the depth first search, hence the entire algorithm is $O(V+E)$ time if the graph is stored as an adjacency list.

This algorithm terminates. We now show it works. If a node is coloured black, then some neighbour has to be white so that it can be coloured black.

Otherwise, a node is coloured white. The visited neighbours of the node (when the node is visited) are black. The subsequent unvisited neighbours of the nodes will not be coloured white as they are adjacent to a node that is coloured white. Hence all neighbours will be coloured black.

Hence, this satisfies your condition.

$\endgroup$
  • $\begingroup$ It is possible to call this $DFS$ many times because it is directed graph, so how can I know sure that 2 white nodes in different forests are not adjacent in directed graph? How to choose the start node ? And to check if any of $x$`s neighbours has been coloured white, everytime, this means exponentially time, right? $\endgroup$ – penguina Dec 27 '15 at 15:51
  • $\begingroup$ @penguina I think I fixed the proof. $\endgroup$ – Element118 Dec 28 '15 at 0:36
  • $\begingroup$ I don’t understand some things. 1. Why we can consider an undirected graph instead of the directed graph? The direction of the adjacency is essential, that a directed edge $(y,x)$ makes only $y$ adjacent to $x$, but not vise versa? 2. Why we can drop the condition? It seems that it cannot be dropped, for instance, for a directed cycle of odd length. 3. Do you call directed of undirected DFS? $\endgroup$ – Alex Ravsky Dec 29 '15 at 13:35
  • $\begingroup$ 4. If in DFS as a neighbor you understand an undirected neighbor, how do you assure in your algorithm that for each black vertex $x$ there exists a white vertex $y$ such that $(y,x)$ is an edge? 5. If in DFS as a neighbor you understand a directed neighbor, how do you assure in your algorithm the absence of the adjacent white vertices? $\endgroup$ – Alex Ravsky Dec 29 '15 at 13:35
  • $\begingroup$ @AlexRavsky Let's start with "no two white colors are adjacent". If 2 white vertices are connected by a directed edge, it violates this condition, so here the edge behaves as it is undirected. "between the white one and the black one exists one directed path of length at most 2", so if there is an edge from the black node to the white node, or from the white node to the black node, it satisfies this criteria. $\endgroup$ – Element118 Dec 30 '15 at 5:45

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.