1
$\begingroup$

Given an directed Graph $G(V,E)$ and a source node $v \in V$. I need to find a partition for $G$ into two sets $X$ and $Y$ in such way that the nodes in $X$ are those that there is a path from $v$ to each of them, and the nodes $Y$ are those that there is no path.

Now, I can use a Depth-first search with $v$ as source node and put the result nodes into $X$ and the other nodes into $Y$ and connect the two sets with the remaining edges. But I want to know if there is an optimal algorithm if exists to do that. (Sorry, I am new into Graph Theory).

$\endgroup$
1
$\begingroup$

DFS is optimal algorithm for this problem. Breadth-first search (BFS) is another optimal algorithm. Both of them take time proportional to the sum of number of vertices and the number of arcs outgoing from $X$ if graph is directed or the number of edges with both ends in $X$ if graph is undirected. This is obviously the best possible time. This bound is true if you use adjacency list for graph storing. If you use adjacency matrix both algorithms become slower, but take $O(|X|\cdot|G|)$ of time that is the best possible in this case.

$\endgroup$
  • $\begingroup$ Thanks . But I want to know if there is an optimal algorithm for the partition part. not the search one . $\endgroup$ – StamDad Apr 26 '17 at 14:03
  • $\begingroup$ As I've said partition problem can't be solved faster, since you need to observe all edges with at least one end in $X$ (and therefore both ends in $X$) or all arcs outgoing from $X$. $\endgroup$ – Smylic Apr 26 '17 at 14:18

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.