Transitive apertures

Posted on by

Sometimes ignorance really is bliss.

If I had normal mathematical training, I would probably know the answers to some of the questions that have been puzzling me lately. But I would have missed the fun of figuring out the answers for myself.

Consider a relation R on some domain, and consider its transitive closure R*. Or, for some purposes, consider its positive transitive closure R+.

Now, sometimes when one is interested both in R and in R*, it seems convenient to have R be as small as it is possible to make it, as long as the transitive closure remains the same. So if there are any ‘redundant’ members of R — members that we can remove without changing R*, we would like to remove them. Since this operation feels like the opposite of transitive closure, I have privately called it “transitive aperture” since I first encountered it nine or ten years ago.

Given two relations R and R’, R’ is a transitive aperture of R if and only if R’ is a subset of R and R’* = R*. R’ is a minimal transitive aperture of R if and only if R’ has no subset R” such that R”* = R’* = R*.

For example: consider the < (less-than) relation on integers. It’s clear (a) that the transitive closure of < is < itself, and (b) that the successor relation on integers (1 = succ(0), 2 = succ(1), etc.) has the same transitive closure. It’s also clear (intuitively — I haven’t tried a proof) that if you omit anything from the successor relation, its transitive closure won’t be <, so the successor relation is apparently a minimal transitive aperture of <.

Now, in all the examples I’ve thought of so far, it’s been obvious both how to calculate the minimal transitive aperture of a given relation, and that there was only one.

But I’ve been asking myself several questions recently. Can I define the notion of minimal transitive aperture cleanly? Does every relation have one? Is it unique? I.e., does every relation have exactly one? Is there an algorithm for finding a minimal transitive aperture for an arbitrary relation?

I spent some time thinking about this today, while driving to Santa Fe and back, and I believe I know some of the answers. I think the definition above is clean and precise. And I think it’s obvious that there’s an algorithm for finding all minimal transitive apertures for any finite relation. (It’s finite, right? Take all the subsets and see if they are (a) a transitive aperture of R and (b) a minimal transitive aperture — if R is finite, then R has a finite number of subsets, so the algorithm will terminate. I didn’t say it was fast, I just said there’s an algorithm.) I don’t know whether there’s an algorithm for infinite relations. And it’s clear that for some relations, there is more than one minimal transitive aperture. But I don’t have time tonight to sketch any of this. I shouldn’t be writing this in the first place, I should be packing for a trip, but I wanted to get at least the formulation of the problem down.

The idea can also be formulated in terms of graphs. Take any directed graph G; you have a set of nodes and a relation on that set. Take the transitive closure of that relation, and draw another graph T with the same set of nodes as G, and arcs representing the transitive closure of the arcs of G. Call T the transitive closure of G, or the reachability graph of G. (For any two nodes n and m, there is an arc from n to m in T if and only if m is reachable from n in G.) A transitive aperture of G is a digraph with the same set of nodes, a subset of G’s arcs, and the same reachability graph.

It’s clear, as I say, that there can be multiple minimal apertures that have the same transitive closure. Any graph of three nodes a, b, c with a cycle among all three nodes a → b → c → a will do to show this: its transitive closure is a complete graph of three nodes. But a → c → b → a has the same transitive closure. QED.

So it’s clear that for digraphs with cycles, there may be multiple minimal transitive apertures.

And for acyclic digraphs?

3 thoughts on “Transitive apertures”

  1. (Sorry, subscripts didn’t go through… Math did for me; hope it does for most.)

    Theorem: Every finite DAG has a unique minimal transitive aperture.

    Proof. To prove the existence of minimal transitive apertures, the exhaustive search algorithm sketched by Michael does the job. To prove uniqueness, we will show that any minimal transitive aperture of a DAG is included in (or equal to) all transitive apertures of that DAG. This will prove uniqueness, because then, any two minimal transitive apertures will have to be mutually included in each other.

    So let G be a DAG, M be a minimal transitive aperture of G, and N an arbitrary transitive aperture of G. We prove (by contradiction) that M ⊆ N.

    Note first that, by definition of transitive aperture (TA), G, M, and N have identical reachability relations (we denote by ⇒H the reachability relation of DAG H). Suppose M is not ⊆ N, i.e., there exists (b, c) ∈ M – N. Since b ⇒M c, we know that b ⇒N c. Let (b, x) ∈ N the first arc in some path from b to c in N. We have (b ⇒N x and x ⇒N c), and thus, (b ⇒M x and x ⇒M c), with x ?~? c. Because M is cycle-free (as are G and N), certainly no path from b to x or from x to c passes through any (b, c) arc. That is, b ⇒M-{(b,c)} c. In other words, we can remove the (b, c) arc from M and it will still be a TA of G, contrary to our hypothesis that it is minimal.

  2. Just found out transitive aperture is usually called “transitive reduction” in maths . The uniqueness result for finite DAGs is mentioned there, as well as a construction algorithm for the non-acyclic case, which I vaguely had in mind.

    For a finite acyclic relation R, I think either of these give you the transitive aperture (or “reduction”) of R:
    R+ – (R+ x R+)
    or R – (R+ x R+).

    OK, got to go on to other things… 🙂

Comments are closed.