1
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Could you provide more specific context? For example, you are assuming the graph is finite? The wikipedia page already says that one can compute transitive reductions in polynomial time. You want better than that, or what? $\endgroup$ Sep 17, 2015 at 11:56
  • $\begingroup$ I updated the question and hope it clarifies what I'm looking for. $\endgroup$ Sep 17, 2015 at 13:17

1 Answer 1

1
$\begingroup$

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}$ .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.