Betweenness problem
From Wikipedia, the free encyclopedia
Betweenness is an algorithmic problem in order theory about ordering a collection of items subject to constraints that some items must be placed between others.[1] It has applications in bioinformatics[2] and was shown to be NP-complete by Opatrný (1979).[3]
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.[1][3]
Examples
As an example, the collection of input triples
- (2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)
is satisfied by the output ordering
- 3, 1, 4, 2, 5
but not by
- 3, 1, 2, 4, 5.
In the first of these output orderings, for all five of the input triples, the middle item of the triple appears between the other two items However, for the second output ordering, item 4 is not between items 1 and 2, contradicting the requirement given by the triple (2,4,1).
If an input contains two triples like (1,2,3) and (2,3,1) with the same three items but a different choice of the middle item, then there is no valid solution. However, there are more complicated ways of forming a set of triples with no valid solution, that do not contain such a pair of contradictory triples.