I have a finite set $P$ of $n$ elements and a topological ordering $R_c$ over $P$, where the transitive closure of $R_c$ is a partial order $R$ of $P$. Finding a linear extension is easy and enumerating them is #P-complete. However, what is the complexity of finding a set of relations $R_c^*$ such that the transitive closure of $R_c^*$ is a linear extension $R^*$ of $R$ and $|R_c^* \setminus R_c |$ is minimal? Let $t(X)$ be the transitive closure of a set of relations $X$, then what we are looking for is
$$ R_c^*\supseteq R_c\; \text{s.t. } \; \not\exists R_c' \; \text{where}\; t(R_c') \;\;\text{is a linear extension of} \;\; t(R_c) \;\;\text{and}\;\; |R_c'| < |R_c^*|$$