<p>The proposed algorithm won't reliably deliver a minimal result because it does nothing to eliminate redundant edges <em>between</em> connected components.</p>
<p>The simplest illustration of this is this acyclic graph with three nodes:</p>
<p><a href="https://i.sstatic.net/3u6zt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3u6zt.png" alt="Graph with edges from 0 to 1, 0 to 2, and 1 to 2" /></a></p>
<p>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.</p>
<p>To guarantee that you really reach a transitive reduction (i.e. a graph with the <em>minimum</em> number of edges), you would want a two-step algorithm along these lines:</p>
<ol>
<li><p>identify connected components and reduce them to simple directed cycles (i.e. run the algorithm in the question)</p>
</li>
<li><p>treat each of these components/cycles as if it were a single node, such that the edges <em>between</em> connected components form a DAG. Run some other algorithm specifically for computing the <em>transitive reduction of a DAG</em> on this.</p>
</li>
</ol>
<p>Since the algorithm proposed in the question simply skips the second step outright, it usually won't return a minimal graph.</p>

CC BY-SA 4.0
2023-07-24T09:28:32.077Z
2023-07-25T11:29:46.783Z
2023-07-25T11:29:46.783Z
Mark Amery
<p>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.</p>

<p>This excerpt from The Algorithm Design Manual has me confused however:</p>

<blockquote>
  <p>"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."</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2015-02-16T15:13:59.767Z
Maybe the non-minimality lies in the edges bridging the components? Some could be removed but here no removal is mentioned.
Denis
CC BY-SA 3.0
2015-02-16T20:00:16.717Z
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.
David Eppstein
CC BY-SA 3.0
2015-02-17T15:31:33.650Z
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...
luegofuego
CC BY-SA 3.0
2015-02-18T00:46:16.720Z
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.
David Eppstein
CC BY-SA 3.0
2015-02-18T08:05:21.533Z
But I don't demand linear time, just polynomial.
luegofuego
CC BY-SA 3.0
2015-03-11T18:13:17.037Z
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).
D.W.
CC BY-SA 4.0
2022-03-27T11:12:28.423Z
@D.W. eh? The question has nothing to do with the time complexity of the algorithm and the comments don't indicate otherwise. leugofuego only mentioned time complexity to point out that he *didn't* care about having a linear time algorithm, in response to David bringing it up. Nor am I sure that he's really got an explanation for the quote. There's still no concrete example of a graph for which the "quick-and-dirty" algorithm delivers a non-minimal result.
Mark Amery
CC BY-SA 4.0
2023-07-24T11:05:06.200Z
Note that the problem is NP-hard, per https://cs.stackexchange.com/questions/86562/finding-a-minimum-equivalent-graph-of-a-digraph
Neal Young
CC BY-SA 4.0
2023-07-25T11:57:05.530Z
@NealYoung the problem of *finding a minimum equivalent graph* is NP-hard, yes, but this question isn't actually about minimum equivalent graphs in any way whatsoever (despite offhandedly mentioning them in the first sentence). Transitive reductions, which this question *is* about, are not NP-hard and can be constructed in polynomial time.
Mark Amery
CC BY-SA 4.0
2023-07-25T12:05:40.563Z
I just discovered a cross-site dupe of this question at https://math.stackexchange.com/q/1150469/71260. I've also realised after reading the tour of Theoretical Computer Science that this question is off-topic here since it's definitely textbook-level (I have never studied CS at all and had to read the definitions of the concepts involved on Wikipedia and was still able to answer it) and such questions aren't meant to live here. I've therefore copied my answer to the cross-site dupe and will flag *this* version of the question for closure & deletion.
Mark Amery
CC BY-SA 4.0
2023-07-25T13:18:45.380Z
@MarkAmery, I see what you mean, thanks.
Neal Young
<graph-theory><graph-algorithms>
Transitive reduction not provably minimal
luegofuego
# Transitive reduction not provably minimal

(Asked by: username_0 on 2015-02-16)

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?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Maybe the non-minimality lies in the edges bridging the components? Some could be removed but here no removal is mentioned.  
> **username_2**: 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.  
> **username_0**: 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...  
> **username_2**: 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.  
> **username_0**: But I don't demand linear time, just polynomial.  
> **username_3**: 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).  
> **username_4**: @D.W. eh? The question has nothing to do with the time complexity of the algorithm and the comments don't indicate otherwise. leugofuego only mentioned time complexity to point out that he *didn't* care about having a linear time algorithm, in response to David bringing it up. Nor am I sure that he's really got an explanation for the quote. There's still no concrete example of a graph for which the "quick-and-dirty" algorithm delivers a non-minimal result.  
> **username_5**: Note that the problem is NP-hard, per https://cs.stackexchange.com/questions/86562/finding-a-minimum-equivalent-graph-of-a-digraph  
> **username_4**: @NealYoung the problem of *finding a minimum equivalent graph* is NP-hard, yes, but this question isn't actually about minimum equivalent graphs in any way whatsoever (despite offhandedly mentioning them in the first sentence). Transitive reductions, which this question *is* about, are not NP-hard and can be constructed in polynomial time.  
> **username_4**: I just discovered a cross-site dupe of this question at https://math.stackexchange.com/q/1150469/71260. I've also realised after reading the tour of Theoretical Computer Science that this question is off-topic here since it's definitely textbook-level (I have never studied CS at all and had to read the definitions of the concepts involved on Wikipedia and was still able to answer it) and such questions aren't meant to live here. I've therefore copied my answer to the cross-site dupe and will flag *this* version of the question for closure & deletion.  
> **username_5**: @MarkAmery, I see what you mean, thanks.  

---

## 1 answers

### Answer by username_4 on 2023-07-24. Score: 2

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](https://i.sstatic.net/3u6zt.png)](https://i.sstatic.net/3u6zt.png)

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.


---

