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. It has applications in bioinformatics and was shown to be NP-complete by Opatrný (1979).
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.
I made an algorithm which I will give a pseudo-code for it and I want to find some counter examples.
Given any list of triplets:
start by finding sink vertex(or number) such that this vertex(number) appears only on the sides of the triplets so for example $(2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)$ the only 2 candidates for being a sink(the term from DAG, directed acyclic graph) are $3,5$ let say that we choose $5$ as sink so every triplets where $5$ appears we will have the $5$ be a sink so in $ (3,2,5),(1,4,5),(3,4,5)$ and we start constructing DAG by making the edges $3->2$ and $2->5$ and $1->4,4->5$ and $3->4,4->5$ until we constructed all the edges with $5$ being the sink which means have only in-going edges
for every remaining triplet $(a,b,c)$ if there is a path from $a$ to $b$ or from $a$ to $c$ or from $b$ to $c$ in the graph G we still constructing then we will add these edges $a->b,b->c$ to the graph G, if there is a path from $c$ to $a$ or $c$ to $b$ or $b$ to $a$ then we add the edges $c->b,b->a$ and remove the triplet from the list and continue until we reach one of 2 situations.
the list is empty and then we do a topological sort for the DAG (G) to find a correct ordering of the numbers(vertices).
all the remaining triplets $(a_i,b_i,c_i)$ such that there is no path between any 2 of them like there is no path from any one of vertex(numbers) to any other, in this case we return to $1$ and repeat.
from the above example the 2 triplets that remains are $(2,1,3),(2,4,1)$ since there is path from $1$ to $4$ we will add the edges $1->4,4->2$ and remove the triplet from the list
since there is a path from $3$ to $2$ we will add the edges $3->1$ and $1->2$ and remove the triplet from the list, since the list is empty we try to do topological sort for the graph $G$ and get the ordering $3,1,4,2,5$ which is a valid ordering for this betweenness example.
I have checked this algorithm on a lot of random triplets of random lengths from $3$ to $100$ and it seems fine so far, could anyone give me a counter example or why this algorithm works correctly ?!
As I understood, when iterating Step 1 the algorithm places the new vertex as a new sink. But then the algorithm can terminate for a valid instance, because of wrong sink guesses. Indeed, let we have the Steiner triple system $S(2,3,7)$: $(1,2,3)$, $(1,4,7)$, $(1,5,6)$, $(2,4,6)$, $(2,5,7)$, $(3,4,5)$, and $(3,6,7)$, compatible with the natural order. Thus a sink can be $1$, $3$, or $7$. Choose $1$ as the sink. Then we have the edges $(3,2)$, $(2,1)$, $(7,4)$, $(4,1)$, $(6,5)$, and $(5,1)$ and the reduced list of triples: $(2,4,6)$, $(2,5,7)$, $(3,4,5)$, and $(3,6,7)$. Thus a new sink can be $2$, $3$, or $7$. Choose $7$ as the sink. Then we have the edges $(2,5)$, $(5,7)$, $(3,6)$, and $(6,7)$, and the reduced list of triples: $(2,4,6)$ and $(3,4,5)$. But the latter is incompatible with the order induced by the present edges $(3,6)$, $(6,5)$, $(5,7)$, and $(7,4)$, a failure.