Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be created, you can simply replace any SCC with a simple Hamiltonian cycle.

This excerpt from The Algorithm Design Manual has me confused however:

"A linear-time, quick-and-dirty transitive reduction algorithm identifies the strongly connected components of G, replaces each by a simple directed cycle, and adds these edges to those bridging the different components. Although this reduction is not provably minimal, it is likely to be pretty close on typical graphs."

Can anyone explain when this would not be minimal? How is it ever possible to construct a smaller equivalent component than a simple directed cycle?

  • 1
    $\begingroup$ Maybe the non-minimality lies in the edges bridging the components? Some could be removed but here no removal is mentioned. $\endgroup$ – Denis Feb 16 '15 at 15:13
  • 2
    $\begingroup$ Yes, I think Denis is correct. It's easy to get down to at most one edge per pair of SCCs, still in linear time, but identifying the edges that are made redundant by paths through multiple SCCs is slower than that. $\endgroup$ – David Eppstein Feb 16 '15 at 20:00
  • $\begingroup$ Any ideas on references were to look? I'm still struggling to identify what might go wrong. I thought you could minimize each SCC separately, and then minimize the condensed/acyclic equivalent graph, as a whole without having to worry about reachability issues between SCCs... $\endgroup$ – luegofuego Feb 17 '15 at 15:31
  • 1
    $\begingroup$ I think you can do exactly that. But to minimize the condensation you have to do something more than simply trimming down multiple edges between the same two components, and it takes more than linear time. $\endgroup$ – David Eppstein Feb 18 '15 at 0:46
  • 1
    $\begingroup$ You were asking for an explanation why The Algorithm Design Manual wrote that, and I think you now have the answer to your question: you have a clear explanation what the author was likely thinking. If you what you really want is a polynomial-time algorithm, then you should edit the question: instead of asking for an explanation of that excerpt, just delete all of that about the excerpt, and ask whether there is a polynomial-time algorithm to do what you want (and show us what you tried). $\endgroup$ – D.W. Mar 11 '15 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.