Talk:Transitive reduction

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

What about countably infinite graphs? It seems to me that the transitive reduction of the graph of "<" on the integers would be ... 1 -> 2 -> 3 ->... I would argue that it has a minimal number of edges because it has a 1-1 correspondence of edges with vertices, and every vertex needs at least one in-edge and at least one out-edge. Lyonsam 06:25, 19 January 2006 (UTC)Reply

OK, details (with the notation that S is the transitive closure):

1. If S is antisymmetric, then the reduction is unique, if it exists.
2. If S is locally finite then the transitive reduction exists. Possibly the locally bounded chain condition would be adequate. (The field (underlying set) of S must be well-ordered for the proof to work, if S is not antisymmetric.)

Definitions

A transitive binary relation S is locally finite if whenever a S b, {c | a S c S b} is finite.

A transitive binary relation S satisfies the locally bounded chain condition if whenever a S b, the collection of all possible n such that

a S x₁, x₁ S x₂, …, x_n−1 S x_n, and x_n S b, with all x_k distinct

is bounded.

Arthur Rubin | (talk) 18:28, 19 January 2006 (UTC)Reply

It is questionable whether something with 26 citations at citeseer is "well-cited". It is definitely a very decent piece of work, but probably no need to mention that citation count in the article.

IMO the article suffers from a graph-centric organisation, in that it starts out with relations in the summary, but then continues to talk only about graphs. I wanted to add the formula ${\displaystyle R'=R-(R^{+}-D)^{2}}$ (D is the diagonal ${\displaystyle (x,x)}$), but there is no good place to put it as things are organised right now.

85.182.77.242 (talk) 23:45, 23 October 2008 (UTC)Reply

It's also not quite right unless the relation is antisymmetric and pseudo-atomic (or finite). There are minimal reductions if the relation is transitive and quasi-finitary, but it's not that simple. — Arthur Rubin (talk) 01:35, 24 October 2008 (UTC)Reply

Isn't a transitive reduction of a relation required to be a subset of that relation? Rp (talk) 16:23, 16 June 2009 (UTC)Reply

No response, so let me try again with an example: Rp (talk) 17:50, 3 January 2010 (UTC)Reply

A transitive reduction of a relation is not required to be its subrelation, the Aho, Garey, and Ullman paper explicitly mentions that. — Emil J. 14:44, 4 January 2010 (UTC)Reply

Thanks - I have found the article and found this out myself. But it's really confusing not to explain this clearly, considering the name reduction. Rp (talk) 18:01, 6 January 2010 (UTC)Reply

I have come to realize that my confusion was not only caused by cycles, but is also contained within them.

Suppose we define the transitive acyclic reduction TAR(R) of a relation R as follows: give each edge in R weight 0 if it is on a cycle, 1 if it is not; then TAR(R) contains exactly the edges in R that are not connected with a path of total weight > 1. In words: reduce just the acyclic part, without touching the cycles. TAR(R) is still what I would call a reduction: it is unique and a subset of R.

Now consider the cyclic parts: the set of strongly connected components of R. Each component "reduces" to a cycle on each of its elements, but any such cycle will do, and none may be present in the component, so this is neither determinate nor strictly a reduction. Aho et al.'s transitive reduction is the result of doing this component-wise, either before or after taking the TAR - the two are independent. Hence it seems more natural to treat TAR and component reduction as separate operations. Is there any citable work that does this? If there is, it may be helpful to add it to this article. Rp (talk) 11:06, 26 July 2010 (UTC)Reply

Quote:

apply a linear time longest path algorithm in the given directed acyclic path, for each possible choice of starting vertex, and keep the subgraph of edges whose longest path distance is exactly one

What on earth does that mean - especially the underlined part - and what's the source? — Preceding unsigned comment added by 217.43.199.72 (talk) 21:21, 8 February 2013 (UTC)Reply

The underlined part means that you keep an edge uv when the longest path distance from u to v is one, and throw it away otherwise. —David Eppstein (talk) 21:53, 8 February 2013 (UTC)Reply

Thanks, David, but I feel the wording needs to be changed. Perhaps like this:

• collect edges (u,v) such that the longest-path distance from u to v is one, calculating those distances by linear-time search from each possible starting vertex, u. — Preceding unsigned comment added by 217.43.199.72 (talk) 22:01, 8 February 2013 (UTC)Reply

• Please go ahead and change it to something you feel is clearer. —David Eppstein (talk) 22:21, 8 February 2013 (UTC)Reply

Given this description from the article

"If G is an arbitrary directed graph, and H is a graph with the minimum possible number of edges having the same reachability relation as G, then H consists of

• A directed cycle for each strongly connected component of G, connecting together the vertices in this component.
• An edge xy for each edge XY of the transitive reduction of the condensation of G"

It suggest this number might be "product((size(scc) - 1)! for each strongly connected component scc) x product(size(scc_x) x size(scc_y), for each pair (scc_x, scc_y) of connected components that is reachable)".

Do we have a source with the right way to find this number? It would be interesting to add to the article "how many there are". 999333a (talk) 18:19, 14 March 2026 (UTC)Reply