9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nitpick: Unless it is a standard terminology, I would call L a “label list” instead of “labeled list,” because it is a list of labels instead of a list of something with labels. $\endgroup$ – Tsuyoshi Ito Nov 24 '14 at 21:53
  • $\begingroup$ OK, I renamed it. I had just made up the terminology. A more standard term would be just word, which I added. $\endgroup$ – a3nm Nov 25 '14 at 7:28
  • $\begingroup$ A small observation: If S is given as a multiset by repeating duplicate elements, then the problem is in NP because the linear extensions of a poset can be enumerated in polynomial time per output by using backtracking. $\endgroup$ – Tsuyoshi Ito Nov 25 '14 at 20:06
  • $\begingroup$ @TsuyoshiIto: True, I believe this is how the case of unlabeled posets works, so indeed we can extend it to labeled posets in this way... but it doesn't help if the same label lists can be obtained in a large number of possible ways. $\endgroup$ – a3nm Nov 25 '14 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.