The minimum feedback arc set problem is NP-hard for tournaments

A solution of Feedback arc set (FAS) problem as a polynomial equivalent to the Minimum FAS (MFAS) for digraphs and NP-hard for tournaments is presented. The solution is provided by assuming Chebyshev inequality lemmas to the parity matrix of subset-intersection. For any integer z, the lemmas consider matrix whose rows and columns are indexed by the subsets in any order and a matrix of order k=2^z, obtained from this matrix by an arbitrary permutation of the columns. It is proved that for a positive integer divisible by three, there exists a bipartite tournament whose particle set has k vertices. The minimum feedback arc set (FAS) for tournaments are found to be NP-hard assuming that the set of digraph of order n has no cycles of length two. MFAS is bound both above and below by assuming the digraph has no arcs between them and the arcs thus generated above will always contribute atleast to MFAS.