1
$\begingroup$

In a directed graph $G=(V,E)$ we denote a vertex $s\in V$ to be a 'source' if there exists in $G$ a path from $s$ to all other vertices $u \in V$.

The problem asks for an efficient algorithm to return the 'source', in case there isnt any, return false.

I've been able to come up with a naive approach to his problem:

$\forall v\in V$:

Do $DFS(v)$, mark $S_v$ to be the set of vertices contained in DFS tree starting at $v$

if $|S_v|=|V|$, return $v$

After doing this for all $v\in V$, if we finished looping, return false.

This algorithm runs in $O(|V|\cdot (|V|+|E|))$ which is far from what I'm looking for, however I am unsure how to improve this.

EDIT:

Since we know a DAG has a vertex $v$ which $degree_{in}(v)=0$, we can use this fact to solve this problem:

I've come up with a new algorithm with a $O(|V|+|E|)$ runtime:

  1. perform tarjan's algorithm to find SCC's and create the quotient graph $G'$.

(since the quotient is a DAG, we can apply the topological sort algorithm)

  1. perform a topological sort on $G'$, mark $v$ to be the first node after sorting

  2. perform $BFS$ on the first node after sorting.

  3. if any of the paths from $v$ to a node in $G'$ is of length $\infty$ (which means there isnt a path from $v$ to said vertex), return that there is no source vertex.

  4. return $v$

I'm not completely sure about choosing the first vertex after sorting, but it's the only thing that came to mind.

Are there any ways to improve this/simplify in a way that the proving stage would be simpler?

$\endgroup$

1 Answer 1

2
$\begingroup$

Hint: if you find all the strongly connected components in the graph, the quotient graph of the SCCs is a DAG. In this DAG, if there is a meta-node that can reach all the other meta-nodes, you have your answer.

Check out the Wikipedia article on strongly connected components.

A DAG has a source vertex if and only if it is connected and only one vertex has in-degree 0.

$\endgroup$
4
  • $\begingroup$ I'm unsure what a 'quetient graph' is, is it the graph of which you get once you reduce each SCC to a single vertex? $\endgroup$
    – Aishgadol
    Commented Dec 20, 2022 at 10:24
  • 1
    $\begingroup$ Yes, that's right. You "contract" each strongly connected component to one vertex and keep the in-neighborhood and out-neighborhood of the union of the vertices' respective neighborhoods. $\endgroup$
    – Pål GD
    Commented Dec 20, 2022 at 10:37
  • $\begingroup$ Quotient graph on Wikipedia. $\endgroup$
    – Pål GD
    Commented Dec 20, 2022 at 10:38
  • $\begingroup$ I've updated my answer, can you check weather it is correct or that there is an example which disproves it? $\endgroup$
    – Aishgadol
    Commented Dec 20, 2022 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.