In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament. Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial time,if so please give the idea
else please mention proof of NP-completeness
I think I finally understood what is going on here and why we seem to have two conflicting answers: one saying that we can simply apply the directed, vertex version of Menger's theorem / max-flow min-cut, and the other one saying that the problem of finding a separating set of vertices in directed graphs is NP-hard. Obviously I'm no expert on this kind of things, but let's see if I can get these right...

Let $G = (V,E)$ be a directed graph. Let $p, q \in V$ be two distinct nodes. In what follows, $X \subseteq V \setminus \{ p,q \}$ is a subset of nodes that doesn't contain $p$ or $q$. Let $G-X$ be the subgraph of $G$ induced by $V \setminus X$.

Now let's define two (non-standard) terms:


$X$ is a one-way separator if $G-X$ doesn't have any directed path from $p$ to $q$.
$X$ is a two-way separator if $G-X$ doesn't have any directed path from $p$ to $q$ or from $q$ to $p$.


Now I think the situation is as follows:


It's possible to find a minimum-size one-way separator in polynomial time.
However, finding a minimum-size two-way separator is NP-hard.


Some explanations and references:


One-way separators: There is a directed vertex version of Menger's theorem: the maximum number of pairwise internally-disjoint directed paths from $p$ to $q$ = the minimum size a one-way separator. See, for example, p. 205 and Theorem 11.6 of Bondy and Murty's Graph Theory with Applications (1976). (Of course Menger's theorem is an existential result, but a typical proof seems to reduce the problem to max-flow min-cut, which gives a poly-time algorithm. Anyway, the statement of Menger's theorem is already enough to place the problem in NP${}\cap{}$co-NP.)
Two-way separators: These seem to be equal to "node multiway cuts in directed graphs, for $k = 2$ and weights = 1" in this paper that András mentioned. Theorem 1 claims that finding an optimal solution is NP-hard.


(Obviously, we could find a 2-approximation of two-way separators by simply taking the union of two one-way separators. But this isn't necessarily optimal.)



Now if we get back to the original question: isn't it enough to just find a one-way separator, to break the strong connectivity? So isn't the original problem in P?