HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a transitive reduction of a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed)
path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...
from to in exists
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of constructing them. More technically, the reduction is a directed graph that has the same
reachability In graph theory, reachability refers to the ability to get from one Vertex (graph theory), vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of Glossary of graph theory#Basics, ...
relation as . Equivalently, and its transitive reduction should have the same
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
as each other, and the transitive reduction of should have as few edges as possible among all graphs with that property. The transitive reduction of a finite
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(a directed graph without directed cycles) is unique and is a subgraph of the given graph. However, uniqueness fails for graphs with (directed) cycles, and for infinite graphs not even existence is guaranteed. The closely related concept of a minimum equivalent graph is a subgraph of that has the same reachability relation and as few edges as possible. The difference is that a transitive reduction does not have to be a subgraph of . For finite
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
s, the minimum equivalent graph is the same as the transitive reduction. However, for graphs that may contain cycles, minimum equivalent graphs are
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
to construct, while transitive reductions can be constructed in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Transitive reduction can be defined for an abstract
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
on a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
, by interpreting the pairs of the relation as arcs in a directed graph.


In acyclic directed graphs

The transitive reduction of a finite
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
''G'' is a graph with the fewest possible edges that has the same
reachability In graph theory, reachability refers to the ability to get from one Vertex (graph theory), vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of Glossary of graph theory#Basics, ...
relation as the original graph. That is, if there is a path from a vertex ''x'' to a vertex ''y'' in graph ''G'', there must also be a path from ''x'' to ''y'' in the transitive reduction of ''G'', and vice versa. Specifically, if there is some path from x to y, and another from y to z, then there may be no path from x to z which does not include y. Transitivity for x, y, and z means that if x < y and y < z, then x < z. If for any path from y to z there is a path x to y, then there is a path x to z; however, it is not true that for any paths x to y and x to z that there is a path y to z, and therefore any edge between vertices x and z are excluded under a transitive reduction, as they represent walks which are not transitive. The following image displays drawings of graphs corresponding to a non-transitive binary relation (on the left) and its transitive reduction (on the right).
The transitive reduction of a finite
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
''G'' is unique, and consists of the edges of ''G'' that form the only path between their endpoints. In particular, it is always a spanning subgraph of the given graph. For this reason, the transitive reduction coincides with the minimum equivalent graph in this case. In the mathematical theory of
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s, any relation ''R'' on a set ''X'' may be thought of as a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
that has the set ''X'' as its vertex set and that has an arc ''xy'' for every
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
of elements that are related in ''R''. In particular, this method lets
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
s be reinterpreted as directed acyclic graphs, in which there is an arc ''xy'' in the graph whenever there is an order relation ''x'' < ''y'' between the given pair of elements of the partial order. When the transitive reduction operation is applied to a directed acyclic graph that has been constructed in this way, it generates the
covering relation In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically expres ...
of the partial order, which is frequently given visual expression by means of a
Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...
. Transitive reduction has been used on networks which can be represented as directed acyclic graphs (e.g.
citation graph A citation graph (or citation network), in information science and bibliometrics, is a directed graph that describes the citations within a collection of documents. Each vertex (or node) in the graph represents a document in the collection, an ...
s or citation networks) to reveal structural differences between networks.


In graphs with cycles

In a finite graph that has cycles, the transitive reduction may not be unique: there may be more than one graph on the same vertex set that has a minimum number of edges and has the same reachability relation as the given graph. Additionally, it may be the case that none of these minimum graphs is a subgraph of the given graph. Nevertheless, it is straightforward to characterize the minimum graphs with the same reachability relation as the given graph ''G''. 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 Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
for each
strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
of ''G'', connecting together the vertices in this component *An edge ''xy'' for each edge ''XY'' of the transitive reduction of the
condensation Condensation is the change of the state of matter from the gas phase into the liquid phase, and is the reverse of vaporization. The word most often refers to the water cycle. It can also be defined as the change in the state of water vapor to ...
of ''G'', where ''X'' and ''Y'' are two strongly connected components of ''G'' that are connected by an edge in the condensation, ''x'' is any vertex in component ''X'', and ''y'' is any vertex in component ''Y''. The condensation of ''G'' is a directed acyclic graph that has a vertex for every strongly connected component of ''G'' and an edge for every two components that are connected by an edge in ''G''. In particular, because it is acyclic, its transitive reduction can be defined as in the previous section. The total number of edges in this type of transitive reduction is then equal to the number of edges in the transitive reduction of the condensation, plus the number of vertices in nontrivial strongly connected components (components with more than one vertex). The edges of the transitive reduction that correspond to condensation edges can always be chosen to be a subgraph of the given graph ''G''. However, the cycle within each strongly connected component can only be chosen to be a subgraph of ''G'' if that component has a
Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, something that is not always true and is difficult to check. Because of this difficulty, it is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
to find the smallest subgraph of a given graph ''G'' with the same reachability (its minimum equivalent graph).


Computational complexity

As Aho et al. show, when the
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of graph algorithms is measured only as a function of the number ''n'' of vertices in the graph, and not as a function of the number of edges, transitive closure and transitive reduction of directed acyclic graphs have the same complexity. It had already been shown that transitive closure and
multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
of Boolean matrices of size ''n'' × ''n'' had the same complexity as each other,Aho et al. credit this result to an unpublished 1971 manuscript of Ian Munro, and to a 1970 Russian-language paper by M. E. Furman. so this result put transitive reduction into the same class. The best exact algorithms for matrix multiplication, as of 2015, take time O(''n''2.3729), and this gives the fastest known worst-case time bound for transitive reduction in dense graphs.


Computing the reduction using the closure

To prove that transitive reduction is as easy as transitive closure, Aho et al. rely on the already-known equivalence with Boolean matrix multiplication. They let ''A'' be the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
of the given directed acyclic graph, and ''B'' be the adjacency matrix of its transitive closure (computed using any standard transitive closure algorithm). Then an edge ''uv'' belongs to the transitive reduction if and only if there is a nonzero entry in row ''u'' and column ''v'' of matrix ''A'', and there is a zero entry in the same position of the matrix product ''AB''. In this construction, the nonzero elements of the matrix ''AB'' represent pairs of vertices connected by paths of length two or more.


Computing the closure using the reduction

To prove that transitive reduction is as hard as transitive closure, Aho et al. construct from a given directed acyclic graph ''G'' another graph ''H'', in which each vertex of ''G'' is replaced by a path of three vertices, and each edge of ''G'' corresponds to an edge in ''H'' connecting the corresponding middle vertices of these paths. In addition, in the graph ''H'', Aho et al. add an edge from every path start to every path end. In the transitive reduction of ''H'', there is an edge from the path start for ''u'' to the path end for ''v'', if and only if edge ''uv'' does not belong to the transitive closure of ''G''. Therefore, if the transitive reduction of ''H'' can be computed efficiently, the transitive closure of ''G'' can be read off directly from it.


Computing the reduction in sparse graphs

When measured both in terms of the number ''n'' of vertices and the number ''m'' of edges in a directed acyclic graph, transitive reductions can also be found in time O(''nm''), a bound that may be faster than the matrix multiplication methods for
sparse graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...
s. To do so, apply a
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
longest path algorithm in the given directed acyclic graph, for each possible choice of starting vertex. From the computed longest paths, keep only those of length one (single edge); in other words, keep those edges (''u'',''v'') for which there exists no other path from ''u'' to ''v''. This O(''nm'') time bound matches the complexity of constructing transitive closures by using
depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
or
breadth first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...
to find the vertices reachable from every choice of starting vertex, so again with these assumptions transitive closures and transitive reductions can be found in the same amount of time.


Notes


References

*. *. *. *.


External links

* {{DEFAULTSORT:Transitive Reduction Set theory Graph theory Graph algorithms de:Transitive_Hülle_(Relation)#Transitive_Reduktion