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.
If every sequence has length 3, the problem is known as Betweenness. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard. 

The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing, 8(1):111—114, Feb. 1979.

[2] B. Chor and M. Sudan. A geometric approach to betweenness, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.

Edits: clarified that the decision version of the problem is NP-hard.