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 -


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



n -> a;
n -> e;





  • $\begingroup$ 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) $\endgroup$ – Lyndon Maydwell Feb 24 '16 at 21:35
  • $\begingroup$ What does it mean for a graph to be "initial"? $\endgroup$ – David Richerby Feb 24 '16 at 22:20

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

| cite | improve this answer | |
  • $\begingroup$ That's true, so I guess I'm asking for an algorithm that will find the sources. $\endgroup$ – Lyndon Maydwell Feb 24 '16 at 22:12
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 24 '16 at 22:13

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.