8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ possible duplicate of FINDING A MAXIMUM ACYCLIC SUB TOURNAMENT GIVEN TWO ACYCLIC SUB TOURNAMENTS $\endgroup$ – Dave Clarke Oct 5 '10 at 9:50
  • $\begingroup$ Sorry. Just read all comments in duplicate. This is a valid repost. Ignore my vote to close. $\endgroup$ – Dave Clarke Oct 5 '10 at 10:24
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 5 '10 at 14:23
  • $\begingroup$ @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 $\endgroup$ – Prabu Oct 5 '10 at 17:14
  • $\begingroup$ What is the difference between S1 and s1? $\endgroup$ – Tsuyoshi Ito Mar 1 '11 at 22:05
0
$\begingroup$

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<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 proved

please see and verify.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Serge Gaspers Mar 21 '11 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.