# What edge-set is required to make a non-cyclic directed disconnected graph initial?

Is there an algorithm to find the minimum set of edges required from a new node in order to make a disconnected directed graph initial?

Example -

input:

a -> b;
b -> c;
b -> d;
e -> f;
f -> g;


output:

n -> a;
n -> e;


Result:

Thanks!

• I imagine that it will be some kind of fixed-point function on the set of nodes, like: target_nodes = fixedpoint (rewrite (reverse edges)) (setof nodes) – Lyndon Maydwell Feb 24 '16 at 21:35
• What does it mean for a graph to be "initial"? – David Richerby Feb 24 '16 at 22:20

## 1 Answer

Assuming that "initial" means connected and having a single source, you can do no better than adding an edge to each source.

• That's true, so I guess I'm asking for an algorithm that will find the sources. – Lyndon Maydwell Feb 24 '16 at 22:12
• Take that as a programming exercise. The exact details depend on the way your digraph is stored. Use the fact that a vertex is a source iff its in-degree is 0. – Yuval Filmus Feb 24 '16 at 22:13