Is there any general approach for trimming a reflexive relation to a partial order on a finite set?
In particular, given a relation R defined on a finite set, which is reflexive xRx, and for all x $\ne$ y, xRy or yRx, but not both; is there a minimal/optimal way to get to a partial order by deleting (x,y) pairs from the relation R?
It is obvious that we can identify a reflexive relation $R\subset V\times V$ with a digraph $G=(V,E)$ where $E=R \setminus \{(x,x)\}_{x\in V}$ (more explicitly, there is an edge $x \rightarrow y$ whenever $xRy$ and $x\neq y$).
Now, remove cycles minimally to end up with a graph $G^\prime$. The corresponding relation $R^\prime$ is not a partial order yet, since it might not satisfy transitivity.
Make $G^{\prime\prime}$ by adding in all edges in order to satisfy transitivity (i.e., if there are edges $x_1 \rightarrow x_2$ and $x_2 \rightarrow x_3$, add the edge $x_1 \rightarrow x_3$). The corresponding relation $R^{\prime\prime}$ is what you are looking for.
(I recommend drawing some pictures to understand what I've said, assuming I've not made any mistakes).