<p>consider the reduction from vertex cover to the above problem. </p>

<p>consider graph $G(V,E)$ with vertex V={1,2,..n}</p>

<p>let T be the tournament with vertices $x_{i},y_{i},z_{i}$ for vertex i=1,2...n</p>

<p>construct 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.</p>

<p>Example for the construction</p>

<p>consider the graph G(V,E) with vertex set {1,2,3} and edges be (1,2)(2,3)
construction as follows</p>

<p>Tournament has vertices $x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$
with construction as follows</p>

<p>Step1 
$x_{1}$ has directed edges to all vertices.</p>

<p>$y_{1}$ has directed edges to all vertices except $x_{1}$</p>

<p>$z_{1}$ has directed edges to all vertices except $x_{1},y_{1}$</p>

<p>$x_{1}$ has directed edges to all vertices except $x_{1},y_{1},z_{1}$</p>

<p>and repeat the process till all edges for the tournament constructed</p>

<p>step 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 k</p>

<p>one case is clear, if G has a vertex cover of size k then surely T has a fvs of size k</p>

<p>other way is, if there is edge (i,j) where $i&lt;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&lt;k&lt;j$. so picking $x_{i},z_{j}$ will result in better solution.hence proved</p>

<p>please see and verify. </p>

CC BY-SA 2.5
2011-03-21T13:34:16.853Z
Can you please be much more precise? With some very wild guessing, I can imagine how you construct the arcs of $T$, but you should make this clearer. In the proof of your claim, why would a feedback vertex set contain both $x_i$ and $z_j$?
Serge Gaspers
CC BY-SA 2.5
2011-03-12T05:02:06.730Z
2011-03-24T05:31:37.997Z
2011-03-24T05:31:37.997Z
Prabu 
<p>Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$. </p>

<blockquote>
  <p>Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup S_2$? </p>
</blockquote>

<p>Can the given problem be solved in polynomial time? If not please state the NP-Completeness. </p>

<p>By keeping $S_1$ as such and removing only the vertices from $S_2$, an $S&#39;$ maximal acyclic tournament belonging to $S_1 \cup S_2$ can be obtained in polynomial time. The solution $S&#39;$ thus obtained may not be the same as the maximum acyclic sub-tournament $S$.</p>

<p>The polynomial time algorithm is based on compression step in iterative compression algorithm for feedback vertex set in tournament from the paper</p>

<blockquote>
  <p><a href="http://www.google.com.tw/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CB0QFjAA&amp;url=http%3A%2F%2Ftheinf1.informatik.uni-jena.de%2Fpublications%2Ffeedback-set-tournaments-jda09.pdf&amp;ei=luluTb7lNIfMuAPk9eG9AQ&amp;usg=AFQjCNG2FCBXsADF-COlfCqtttHw57N5kA" rel="nofollow">Fixed-parameter tractability results for feedback set problems in tournaments</a>, Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.</p>
</blockquote>

<p>If finding a maximal acyclic sub-tournament $S$ is NP-complete then I have no choice except to find $S&#39;$, so I wish to know whether finding $S$ is NP-complete or not.</p>

CC BY-SA 2.5
2010-10-05T09:50:54.973Z
possible duplicate of [FINDING A MAXIMUM ACYCLIC SUB TOURNAMENT GIVEN TWO ACYCLIC SUB TOURNAMENTS](http://cstheory.stackexchange.com/questions/1142/finding-a-maximum-acyclic-sub-tournament-given-two-acyclic-sub-tournaments)
Dave Clarke
CC BY-SA 2.5
2010-10-05T10:24:20.840Z
Sorry. Just read all comments in duplicate. This is a valid repost. Ignore my vote to close.
Dave Clarke
CC BY-SA 2.5
2010-10-05T14:23:06.630Z
Are you removing arcs or vertices from the union? In other words is your problem like feedback arc set or feedback vertex set? Your question isn't entirely clear and the two sorts of problem are quite different.
Warren Schudy
CC BY-SA 2.5
2010-10-05T17:14:14.033Z
@Warren It is a feedback vertex set problem.First problem Given T1 and T2 acyclic sub-tournament of T. Feedback vertex set should belong to T1 (can be found in polynomial time) ,whereas in the second problem , Feedback vertex set can present be in  both T1 and T2.My question is whether second one can be solved in polynomial time
Prabu 
CC BY-SA 2.5
2011-03-01T22:05:57.367Z
What is the difference between S1 and s1?
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-02T15:11:33.470Z
there is no difference between s1 and S1. Sorry for the confusion
Prabu 
<ds.algorithms><np-hardness><graph-algorithms>
Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments
Prabu 
# Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

(Asked by: username_0 on 2010-10-05)

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 paper

> [Fixed-parameter tractability results for feedback set problems in tournaments](http://www.google.com.tw/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http%3A%2F%2Ftheinf1.informatik.uni-jena.de%2Fpublications%2Ffeedback-set-tournaments-jda09.pdf&ei=luluTb7lNIfMuAPk9eG9AQ&usg=AFQjCNG2FCBXsADF-COlfCqtttHw57N5kA), Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

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.

**Tags:** ds.algorithms, np-hardness, graph-algorithms

> **Comments:**
> **username_1**: possible duplicate of [FINDING A MAXIMUM ACYCLIC SUB TOURNAMENT GIVEN TWO ACYCLIC SUB TOURNAMENTS](http://cstheory.stackexchange.com/questions/1142/finding-a-maximum-acyclic-sub-tournament-given-two-acyclic-sub-tournaments)  
> **username_1**: Sorry. Just read all comments in duplicate. This is a valid repost. Ignore my vote to close.  
> **username_2**: Are you removing arcs or vertices from the union? In other words is your problem like feedback arc set or feedback vertex set? Your question isn't entirely clear and the two sorts of problem are quite different.  
> **username_0**: @Warren It is a feedback vertex set problem.First problem Given T1 and T2 acyclic sub-tournament of T. Feedback vertex set should belong to T1 (can be found in polynomial time) ,whereas in the second problem , Feedback vertex set can present be in  both T1 and T2.My question is whether second one can be solved in polynomial time  
> **username_3**: What is the difference between S1 and s1?  
> **username_0**: there is no difference between s1 and S1. Sorry for the confusion  

---

## 1 answers

### Answer by username_0 on 2011-03-12. Score: 0 | Accepted answer

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...n

construct 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 construction

consider the graph G(V,E) with vertex set {1,2,3} and edges be (1,2)(2,3)
construction as follows

Tournament has vertices $x\_{1},y{1},z{1},x\_{2},y\_{2},z\_{2},x\_{3},y\_{3},z\_{3}$
with construction as follows

Step1
$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 constructed

step 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 k

one case is clear, if G has a vertex cover of size k then surely T has a fvs of size k

other way is, if there is edge (i,j) where $i

please see and verify.

> **Comments:**
> **username_4**: Can you please be much more precise? With some very wild guessing, I can imagine how you construct the arcs of $T$, but you should make this clearer. In the proof of your claim, why would a feedback vertex set contain both $x_i$ and $z_j$?  

---

