0
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 18:13

1 Answer 1

Reset to default
2
$\begingroup$

The proposed algorithm won't reliably deliver a minimal result because it does nothing to eliminate redundant edges between connected components.

The simplest illustration of this is this acyclic graph with three nodes:

Graph with edges from 0 to 1, 0 to 2, and 1 to 2

The algorithm in the question simply returns this graph as-is, with no edges removed. This is not minimal; the edge from 0 to 2 is redundant and can be removed.

To guarantee that you really reach a transitive reduction (i.e. a graph with the minimum number of edges), you would want a two-step algorithm along these lines:

  1. identify connected components and reduce them to simple directed cycles (i.e. run the algorithm in the question)

  2. treat each of these components/cycles as if it were a single node, such that the edges between connected components form a DAG. Run some other algorithm specifically for computing the transitive reduction of a DAG on this.

Since the algorithm proposed in the question simply skips the second step outright, it usually won't return a minimal graph.

Improve this answer
$\endgroup$

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