How to solve this partial order reduction in $O(n^2)$?
I think I am able to solve it.

First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)].

Phrased another way, this algorithm will find all "successors" for each of the elements in the first sequence. Finding successors for each element will take O(n) time.

For i in range(0,n):
    initialize most_recent_successor to None
    For j in range(i+1, n):
        if pos. of seq_1[j] &gt; pos. of most_recent_successor in both sequences:
            advance j
        else:
            most_recent_successor = seq_1[j]
            add (seq_1[i], seq_1[j]) to result


Essentially, if a valid pair (seq_1[i], seq_1[j]) exists, then any pair (seq_1[i], seq_1[k]) will not be valid if the position of seq_1[k] in comes after the position of seq_1[j] in both sequences.

So, for the example in the question, (1, 3) is a valid pair. Therefore, (1,4) and (1, 5) are not valid pairs since 4 and 5 come after 3 in both sequences.

Edit: Please look at ruakh's insightful answer on lookup arrays I used here.