# Identify a graph coloring problem in graph theory

Suppose a directed graph $$G=(V,E)$$ and an initial subset of colored nodes $$R_{0} \subseteq V$$. We then produce the following subsets $$R_{1} \subseteq R_{2} \subseteq ..\subseteq R_{n}$$ with the following iterative procedure:

$$R_{1} = R_{0} \cup \{v\;|\; \forall (w,v) \in E: w \in R_{0}\}$$

and generally

$$R_{i+1} = R_{i} \cup \{v\;|\; \forall (w,v) \in E: w \in R_{i}\}$$

Essentially, at each step of the iteration, we color a node if all of it's incoming edges originate from nodes that have already been colored.

This procedure can have two outcomes, (a) all nodes eventually get colored at a step $$j$$ of the iteration such that $$R_{j}=V$$ or (b) an iteration is reached where no other nodes can get colored and some remain uncolored ($$R_{j} = R_{j+1} \subset V$$).

Now, the problem is to compute the smallest possible inital set $$R_{0}$$ such that eventually all nodes will be colored. My questions are:

a) Does this problem have a name in the literature of graph theory?

b) If so, are there any efficient algorithmic solutions?

Thank you!

If the graph is non-oriented (that is, $$(u,v) \in E \Leftrightarrow (v,u) \in E$$), then you're looking for a vertex cover of the graph. Indeed, if an edge $$(u,v)$$ has none of its ends in $$R_0$$, this will be a deadlock preventing both $$u$$ and $$v$$ from ever getting in one of the $$R_i$$ ; and if you have a vertex cover for $$R_0$$ then $$R_1 = V$$.
• 1) So the problem as I defined it is at least as hard as vertex cover? 2) The question "does a solution $R_{0}$ with less than k nodes exist?" is an NP problem because if you are given a solution $R_{0}$ with less than k nodes you can verify it fast by expanding to $R_{1}, ..., R_{k}$. From (1) & (2) is it correct to say that the problem is NP-hard? Jan 26 at 21:13
• What About the constraint that the graph is directed and the source of the edges are in $R_i$ and the targets in $R_{i+1}$? Jan 27 at 7:47
• @DavidScholz a non-directed graph can be interpreted as a directed graph with two oriented edges for each non-oriented edge (in this case, it's OK to do so because we don't examinate properties on the edges themselves). My argument is : if you have a non-oriented edge (u,v), that is both u->v and v->u, if ($u \notin R_i$ and $v \notin R_i$) then ($u \notin R_{i+1}$ and $v \notin R_{i+1}$) so both won't appear anytime in the process. Jan 27 at 10:02