Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$. Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup S_2$? Can the given problem be solved in polynomial time? If not please state the NP-Completeness. By keeping $S_1$ as such and removing only the vertices from $S_2$, an $S'$ maximal acyclic tournament belonging to $S_1 \cup S_2$ can be obtained in polynomial time. The solution $S'$ thus obtained may not be the same as the maximum acyclic sub-tournament $S$.The polynomial time algorithm is based on compression step in iterative compression algorithm for feedback vertex set in tournament from the paperFixed-parameter tractability results for feedback set problems in tournaments, Michael Dom, Jiong Guo, Falk Hffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 7686.If finding a maximal acyclic sub-tournament $S$ is NP-complete then I have no choice except to find $S'$, so I wish to know whether finding $S$ is NP-complete or not.
Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments
ds.algorithms;np hardness;graph algorithms
consider the reduction from vertex cover to the above problem. consider graph $G(V,E)$ with vertex V={1,2,..n}let T be the tournament with vertices $x_{i},y_{i},z_{i}$ for vertex i=1,2...nconstruct the tournament with edges in order of  $x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}...x_{n},y_{n},z_{n}$.if there exist a edge(i,j) then $z_{j},x_{i}$.  $x_{i},y_{i}$ belongs to $T_{1}$ for i=1,2...n and $z_{i}$ belongs to $T_{2}$ for i=1,2...n. It is clear that $T_{1}$ and $T_{2}$ are acyclic.Example for the constructionconsider the graph G(V,E) with vertex set {1,2,3} and edges be (1,2)(2,3)construction as followsTournament has vertices $x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$with construction as followsStep1 $x_{1}$ has directed edges to all vertices.$y_{1}$ has directed edges to all vertices except $x_{1}$$z_{1}$ has directed edges to all vertices except $x_{1},y_{1}$$x_{1}$ has directed edges to all vertices except $x_{1},y_{1},z_{1}$and repeat the process till all edges for the tournament constructedstep 2: (1,2) has a edge so swap the edge direction from $(x_{1},y_{2})$ to $(y_{2},x_{1})$ similarly for (1,3)claim: G has a vertex cover of size k only if T has feedback vertex set of size kone case is clear, if G has a vertex cover of size k then surely T has a fvs of size kother way is, if there is edge (i,j) where $i<j$ if both $x_{i},z_{j}$ is not picked into the solution then we are forced to pick all vertices $y_{i},z_{i},x_{k},y_{k},z_{k},x_{j},y_{j}$ where for all k such that $i<k<j$. so picking $x_{i},z_{j}$ will result in better solution.hence provedplease see and verify. 