Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is a finite sequence $L$ of elements of $\Sigma$ (formally $L$ maps every position $i \in \{1, \ldots, |L|\}$ to a label $L[i] \in \Sigma$, where $|L|$ is the length of $L$). We say that $L$ is a linear extension of $P$ if there is an order- and value-preserving bijection $f$ from $P$ to $L$: formally, $f$ is a bijection from $P$ to $\{1, \ldots, |L|\}$, we have $\forall x, y \in P$, if $x < y$ then $f(x) < f(y)$, and $\forall x \in P$, $\mu(x) = L[f(x)]$.
My question is to determine the complexity of the following problem: I am given as input a set $S$ of label lists, and I want to know if there exists a labeled poset $P_S$ such that $S$ is exactly the set of the linear extensions of $P_S$. (Also, if possible, compute $P_S$.)
For instance, for the input $S = \{(A, B, A), (A, A, B)\}$, a choice of labeled poset would be $P_S = (\{a_1, a_2, b\}, <_S, \mu_S)$, where $<_S = \{a_1 < a_2, a_1 < b\}$ and $\mu_S$ maps $a_1$ and $a_2$ to $A$ and $b$ to $B$.
Of course, the answer is trivially "no" if all lists of $S$ do not have the same length, or actually if they do not have the same domain of values (seen as a multiset). Conversely, if they do, I can easily construct a labeled poset (e.g., the empty order relation on the domain) such that all label lists of $S$ are linear extensions of the poset. However, can I do this and avoid that other label lists not in $S$ are also extensions?
Other remarks:
The problem can alternatively be phrased in terms of directed labeled graphs and topological sorts: a label list $L$ is a linear extension of a labeled poset $P$ iff it is the label of some topological sort of a labeled transitive DAG $G_P$ that represents $P$ (i.e., its Hasse diagram). So my problem can be equivalently phrased as follows: given $S$, determine if there is a labeled DAG $G_S$ such that $S$ is exactly the set of the labels of the topological sorts of $G_S$.
For the case of ordinary posets (not labeled posets), or equivalently of unlabeled DAGs, the problem is in PTIME. The argument is to construct a candidate poset $P_S$ by intersecting the comparability relations implied by $S$ (which you cannot do in the labeled case because of the ambiguity of labels), and then check that $P_S$ realizes no other linear extensions by enumerating them (you cannot tractably do this with labels because there may be a lot of "linear extensions" that end up being the same label set). This implies that the problem is in PTIME if the list $L$ contains no duplicate values, or if $\mu$ is injective.
Other related results are the fact that counting the number of linear extensions of an input labeled poset (actually, even when there are no labels), is #P-hard. This does not imply hardness of my problem, though, because enumeration approaches could conceivably work though they do not directly adapt (see above). Also, from an answer to a previous question I know that it is NP-hard, given a labeled poset $P$ and label list $L$, to determine whether $L$ is a linear extension of $P$; yet I see no easy reduction between that problem and the question asked here.
I am not even sure that my problem is in NP. Of course we can try to guess the poset $P_S$ and bijections that realize the linear extensions of $S$, but then we need to verify the absence of other linear extensions, so this only gives a $\Sigma_2^P$ upper bound.
