Skip to main content
edited tags
Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185
Tweeted twitter.com/#!/StackCSTheory/status/218835003998609408
Source Link
Suresh Venkat
  • 32.2k
  • 4
  • 97
  • 272

A question on linear extensions of partial orders

If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with each of the partial orders).

I've come across a variation:

Fix a set $V$. You're given sequences $\sigma_1, \ldots \sigma_k$ of elements drawn from $V$ without repetition (the sequences are of length between 1 and $|V|$).

Is there a way to fix orientations for each of the sequences (either forward or reverse) so that the resulting collection of chains (viewed as a partial order) admits an extension ?

Is this problem well-known ?

Note: The orientation is chosen for an entire sequence. So if the sequence is $1-2-4-5$, you can either keep it that way, or flip it to $5-4-2-1$, but you can't do anything else.