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?