Editing Betweenness problem (section)

==Complexity==
{{harvtxt|Opatrný|1979}} showed that the [[Decision problem|decision version]] of the betweenness problem (in which an algorithm must decide whether or not there exists a valid solution) is [[NP-complete]] in two ways, by a [[Reduction (complexity)|reduction]] from [[3-satisfiability]] and also by a different reduction from [[hypergraph]] [[graph coloring|2-coloring]].<ref name="o79">{{citation
 | last = Opatrný | first = J.
 | doi = 10.1137/0208008
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 522973
 | pages = 111–114
 | title = Total ordering problem
 | volume = 8
 | year = 1979}}.</ref> However, it can easily be solved when all unordered triples of items are represented by an ordered triple of the input, by choosing one of the two items that are not between any others to be the start of the ordering and then using the triples involving this item to compare the relative positions of each pair of remaining items.

The related problem of finding an ordering that maximizes the number of satisfied triples is [[SNP (complexity)|MAXSNP-hard]], implying that it is impossible to achieve an [[approximation ratio]] arbitrarily close to&nbsp;1 in [[polynomial time]] unless [[P = NP]].<ref name="cs98"/> It remains hard to solve or approximate even for dense instances that include an ordered triple for each possible unordered triple of items.<ref>{{citation
 | last1 = Ailon | first1 = Nir
 | last2 = Alon | first2 = Noga | author2-link = Noga Alon
 | doi = 10.1016/j.ic.2007.02.006
 | issue = 8
 | journal = [[Information and Computation]]
 | mr = 2340896
 | pages = 1117–1129
 | title = Hardness of fully dense problems
 | volume = 205
 | year = 2007| doi-access = free
 }}.</ref> 
The minimum version of the problem restricted to the tournaments was proven to have polynomial time approximation schemes (PTAS).<ref>
{{citation
 | last1 = Karpinski | first1=Marek
 | last2 = Schudy    | first2=Warren
 | contribution=Approximation schemes for the betweenness problem in tournaments and related ranking problems
 | editor = L.A. Goldberg and K. Jansen and R.Ravi and J.D.P. Rolim
 | title = Proc. APPROX 2011, RANDOM 2011
 | series = [[Lecture Notes in Computer Science]]
 | volume = 6845
 | year=2011
 | pages=277–288
 | doi = 10.1007/978-3-642-22935-0_24
| arxiv = 0911.2214
 | isbn=978-3-642-22934-3
 | s2cid=7180847
 }}
</ref> One can achieve an approximation ratio of 1/3 (in expectation) by ordering the items randomly, and this simple strategy gives the best possible polynomial-time approximation if the [[unique games conjecture]] is true.<ref>{{citation
 | last1 = Charikar | first1 = Moses | author1-link = Moses Charikar
 | last2 = Guruswami | first2 = Venkatesan | author2-link = Venkatesan Guruswami
 | last3 = Manokaran | first3 = Rajsekar
 | contribution = Every permutation CSP of arity 3 is approximation resistant
 | doi = 10.1109/CCC.2009.29
 | mr = 2932455
 | pages = 62–73
 | title = 24th Annual IEEE Conference on Computational Complexity
 | year = 2009| isbn = 978-0-7695-3717-7 | s2cid = 257225 }}.</ref> It is also possible to use [[semidefinite programming]] or combinatorial methods to find an ordering that satisfies at least half of the triples of any satisfiable instance, in polynomial time.<ref name="cs98"/><ref>{{citation
 | last = Makarychev | first = Yury
 | doi = 10.1016/j.orl.2012.08.008
 | issue = 6
 | journal = Operations Research Letters
 | mr = 2998680
 | pages = 450–452
 | title = Simple linear time approximation algorithm for betweenness
 | volume = 40
 | year = 2012}}.</ref>

In [[parameterized complexity]], the problem of satisfying as many constraints as possible from a set ''C'' of constraints is [[fixed-parameter tractable]] when parameterized by the difference ''q''&nbsp;&minus;&nbsp;|''C''|/3 between the solution quality ''q'' found by the parameterized algorithm and the |''C''|/3 quality guaranteed in expectation by a random ordering.<ref>{{citation
 | last1 = Gutin | first1 = Gregory | author1-link = Gregory Gutin
 | last2 = Kim | first2 = Eun Jung | author2-link = Eun Jung Kim (parameterized complexity)
 | last3 = Mnich | first3 = Matthias
 | last4 = Yeo | first4 = Anders
 | doi = 10.1016/j.jcss.2010.05.001
 | issue = 8
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 2722353
 | pages = 872–878
 | title = Betweenness parameterized above tight lower bound
 | volume = 76
 | year = 2010| arxiv = 0907.5427
 | s2cid = 3408698
 }}.</ref>

Although not guaranteed to succeed, a [[greedy heuristic]] can find solutions to many instances of the betweenness problem arising in practice.<ref name="sksl97"/>