1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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$.

Even in this subclass of graphs, the problem already is NP-hard, so I guess the answer to b) is no. But for the vertex cover problem there are approximation algorithms, so maybe you could look there to find something similar for your problem...

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Enk9456
    Jan 26 at 21:13
  • $\begingroup$ I meant to say that the problem is NP-complete, because (1) implies it is in NP-hard and (2) it is in NP? $\endgroup$
    – Enk9456
    Jan 26 at 21:24
  • $\begingroup$ 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}$? $\endgroup$ Jan 27 at 7:47
  • $\begingroup$ @Enk9456 yes, for both (1) and (2), it is indeed NP-complete. $\endgroup$
    – Hugo Manet
    Jan 27 at 9:55
  • $\begingroup$ @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. $\endgroup$
    – Hugo Manet
    Jan 27 at 10:02

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.