Problem Statement
The input to a betweenness problem is a collection of ordered triples of items. The items listed in these triples should be placed into a total order, with the property that for each of the given triples, the middle item in the triple appears in the output somewhere between the other two items. The items of each triple are not required to be consecutive in the output
There are two versions of the problem defined as follows
The Decision version of the betweenness problem in which an algorithm must decide whether or not there exists a valid solution?
The Normal (Hard) version of the betweenness problem in which an algorithm must provide a total ordering which satisfies the conditions or says NO when there no solution can be found.
in the original published paper, where Opatrný (in 1979) showed that its decision problem is NP-Complete, it has been defined precisely as a Total ordering problem
definition. The Total Ordering Problem (TOP) is the following: given a finite set S and a set of ordered triples R $\subseteq$ SxSxS determine whether there exists a total ordering of S such that for any element (a,, b, c) in R either a < b, b < c or c < b, b < a (we say that such an ordering satisfies R). A solution for TOP would be an algorithm which takes an instance (S, R) of TOP and outputs true if and only if there exists a total ordering of S satisfying R.
Question
Is there a proposed nontrivial example (for intuition) in which there will be NO answer for the betweenness decision problem?
means there is no total ordering of $S$ exists that satisfying R
My works
I came up with this example, but the bi-orientation nature of answers makes it possible to find the answer.
$(a,b,c) \in R$ and $(X, c, b) \in R$ for $X \ne a$ has solution of abcX
I also guess, if a circle appears in the representation graph of R simulation there will be no total ordering, but I'm not sure I'm right or how to prove it.
by graph representation of R, I mean a->b->c if $(a,b,c) \in R$ for all $(ai,bi,ci) \in R$
updated
As @amrsa suggested in the comments there are possibilities for trivial approval or disapproval of the statement. followings are roughly explained
if $R = \{(x,y,z), (a,b,c)\}$ then there is a total ordering of e.g. xyzabc.
if $R=\{(a,b,c), (b,c,a)\}$ then there will not be any ordering.
the second statement may not be the only condition for the nonexistence of total order, cause if it was, we can remove all of them in polynomial time and do the topological sort and the exact answer (I guess).
Reichenbach, H. pointed out that R is not totally orderable when it includes the ordered triples
$(A_1, A_2, A_3), (A_1, A_2, A_4), (A_4, A_2, A_3)$
for each clause, if you fix its orientation you face a contradiction.
for example. let fix reverse order for first clause meaning $(A_3, A_2, A_1)$ so the second clause must rotate to $(A_4, A_2, A_1)$ to be satisfiable beside first clause, till now we have $A_3 < A_2$ and $A_4 < A_2$ but the third caluse says $A_4 < A_2 < A_3$ or $A_3 < A_2 < A_4$ which both states $\bot$ means our first guess was wrong for every other it reachse $\bot$ the same way.
Actually, if we assume any clauses in R to be fixed orientated (meaning we know they will not be rotated), the representation graph must be a DAG.
Reichenbach, H. (1956). The direction of time. Berkeley, Los Angeles: University of California Press.