I have to say that I am newbie in graph theory, so bear with me.
Here is my question:
Assume that you are given:
1. A directed graph G
2. A positive integer K
3. A source node S in graph G.
find the minimum number of edges to be added to graph G so that there is simple path of length K from node S to all the other nodes in the graph?
Does anyone know if this is a np complete problem?
Set cover reduces to this for $K = 2$, so yes it is NP-hard.
The set cover problem can be formulated as this: given a graph $G$ with disjoint vertex sets $X$ and $Y$ and arcs going from $X$ to $Y$, choose a subset $X' \subseteq X$ of minimum cardinality such that for every element $y \in Y$, there is an arc going from $X'$ to $Y$. Thus, $X'$ "covers" $Y$, and is called a covering set.
To reduce this to your problem, add your source vertex $s$, add another vertex $t$, add an arc between $s$ and $t$, and add every arc from $t$ to $X$. It is not too hard to show that if there is a covering set $X'$ of size $k$, then adding $k$ arcs is enough to make $s$ at distance at most $2$ from every vertex (add each arc from $s$ to $X'$).
Conversely, suppose that adding a set $A$ of $k$ arcs makes $s$ at distance at most $2$ from every vertex. We use $A$ to find a covering set of size at most $k$. If every arc of $A$ goes from $s$ to $X$, then the endpoint of the arcs of $A$ must form a covering set, as desired. Suppose instead that there is some arc $(x, y)$ in $A$, for some $x \in X$ and $y \in Y$. Let $x' \in X$ such that $(x', y)$ is an arc of $G$ (we may assume $x'$ exists, otherwise the set cover instance is impossible). In $A$, we may replace $(x, y)$ by $(s, x')$, and $s$ is still at distance at most $2$ from every vertex. We may repeat this for every arc of $A$ from $X$ to $Y$. Observe that we may also do this for every arc from $t$ to $Y$ in $A$, if any. We may also handle arcs of $A$ from $Y$ to $Y$ in the same manner, then arcs of $A$ from $s$ to $Y$, if any. Note that there is no point in having arcs from $Y$ to $X \cup \{s, t\}$, and arcs from $X$ to $X$ can easily be replaced by an arc from $s$ to $X$, so this takes care of every possible type of arc. After these operations, $A$ has only arcs of the form $(s, x)$ for $x \in X$, and the endpoints of $A$ must form a covering set.