Transitive reduction from a linear extension of a partial order Is there an efficient algorithm to create a transitive reduction from a single linear extension of a given partial order?
Update: I'm aware of the time complexity of computing a transitive reduction of a given partial order. What I wanted to know is: given a partial order and one of its linear extensions, can that time complexity be reduced?
 A: The time can be reduced by at least half. A partial order $P$ with a given linear extension allows certain optimizations for transitive reduction that are not available without the extension. These optimizations proceed from the fact that we can immediately produce an upper triangular matrix for the incidence relation -- this is a topological sort. The existence of pairs that will force a given pair $(i,j)$ to be reducible can easily be found by examining only pairs in the upper left of the matrix and on the row $i$ and in column $j$. 
Label the elements of the set in the order given by the linear extension 1 to $n$, where $n$ is the cardinality of the set.
From the incidences of the partial order $P$, label the entries $D[i,j]$ of a matrix $D$ with 1 if $i \leq n$ in $P$ and 0 otherwise. Perform the following on the matrix $D$.
for (j = n; j > 2; j--) // columns
    for (i=1 ; i <= j ; i++) // rows 
         if (D[i,j] == 1) then 
            for (k= i+1 ; k < j ; k++) 
                 if (D[i,k] == 0) then loop
                 if (D[k,j] == 0) then loop
                 set D[i,j] = 0 // eliminate the chords in situ 
                 break // the first match ends it for (i,j)
            endfor
        endif
    endfor
endfor

The transitive reduction of $P$ will be the subdigraph corresponding to the remaining elements of $D$. The maximum number of pair comparisons needed to eliminate any incidence $D[i,j]$ is $(j-i-1)$. Thus the maximum number of pair comparisons overall will be $\sum_{k=2}^{n-1} \binom{k}{2}$ .
