6
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ yes it is a one way separator problem . so it can be solved in polynomial time. thank u $\endgroup$ – Prabu Sep 10 '10 at 16:25
  • $\begingroup$ I just saw this question again after some months (since you retagged it): I hadn't seen your answer yet, but I like it. Nice job! $\endgroup$ – Daniel Apon Nov 11 '10 at 14:45
5
$\begingroup$

Here is a partial answer.

A quick recap from Wikipedia: a tournament has exactly one directed edge between every pair of distinct vertices. Every tournament has a Hamiltonian path, by a simple inductive argument due to Rédei. A strongly connected tournament must then have a Hamiltonian cycle (this is apparently due to Camion).

So a tournament that is not strongly connected is one that does not have a Hamiltonian cycle, yet it has a Hamiltonian path. This means that one is looking for a minimum directed vertex cut; any two vertices s and t can be taken as the source and sink (with the final answer being the lesser of the minimum s-t cut and the minimum t-s cut).

Minimum directed vertex cut with two terminals is NP-hard for general directed graphs, even for unit edge weights, but can be 2-approximated efficiently via linear programming (see Theorems 5 and 8 of Naor and Zosin, A 2-approximation algorithm for the directed multiway cut problem, SIAM J. Comput. 31 477–482). Note that the max-flow min-cut theorem that Daniel's answer and Jukka's comment appeal to applies to edges, not vertices. Vertex cut is harder than edge cut, and this is discussed by Naor and Zosin, as well as Garg, Vazirani, and Yannakakis in their paper Multiway cuts in node weighted graphs (briefly in the 1994 conference version and more fully in the 2004 journal version).

To complete the NP-hardness argument, one should rigorously specify the reduction from min-directed-2-vertex-cut (unit weights) on directed graphs to min-directed-2-vertex-cut (unit weights) on tournaments. This is left as an exercise for the reader (because I can't make it work right now, and it may not be totally trivial, and maybe isn't possible at all...).

So this seems to be an NP-hard problem, and if it does have a polynomial-time algorithm, it seems to require more than just a quick application of max-flow min-cut.

$\endgroup$
  • $\begingroup$ ás: Have you had a look at my answer below? Do you still think this problem is NP-hard? $\endgroup$ – Jukka Suomela Sep 11 '10 at 21:45
  • $\begingroup$ Jukka, your answer seems well-thought-out. I was somewhat ambivalent about NP-hardness, and it seems for good reason. $\endgroup$ – András Salamon Sep 12 '10 at 16:33
3
$\begingroup$

What I've written below is wrong. See Andras's response for a correct answer. I'm leaving this post up in the hopes its errors are instructive for others as they were for me.


I'm not an expert in graph theory, but I'll give it a shot (so please read this with your critical glasses on).

IIRC, a strongly connected tournament is a set of vertices such that for any pair of vertices $p$ and $q$, there is a path from $p$ to $q$. Thus to make a strongly connected tournament a non-strongly connected tournament (i.e. a decisive tournament), you need to cut the graph (i.e., remove a subset of edges s.t. you remove all paths from at least one $p$ to one $q$). Obviously there are many ways to cut the graph, but you want to choose the one that corresponds to the minimum number of vertices removed.

Let all edges have capacity $1$. Consider any two vertices $p_0$ and $q_0$, you can separate all paths between them by finding the max flow (which corresponds to min cut). Then, choose the set of vertices adjacent to the cut that is minimal (there are $O(|V|)$ of them); this is guaranteed to remove the edges of the min cut for $p_0$ and $q_0$. For $p_0$ and $q_0$, this is the $V1$ you were looking for.

Now, loop over all pairs of vertices (there are $|V|^2$ many of them) proceeding as above, to produce a set of candidate-$V1$ sets. Out of the $|V|^2$ candidate-$V1$ sets, choose the smallest, and output.

Naive runtime: $O(|V|^2 \cdot |V| \cdot MF)$ where $MF$ is the runtime of any max-flow algorithm, e.g. Ford-Fulkerson.

Again, I don't spend a lot of time thinking about problems like this, so it would be very good for someone to try to poke holes in it.

$\endgroup$
  • $\begingroup$ I think the right keywords for googling are "strong $k$-connectivity" and the directed, vertex version of Menger's theorem. And yes, checking the directed vertex connectivity for all $n^2$ pairs of nodes and taking the minimum gives the strong connectivity of the whole graph, which seems to be exactly what the original question is about. $\endgroup$ – Jukka Suomela Sep 4 '10 at 13:58
  • $\begingroup$ First take two vertices, find min cut for these two vertices using max flow min cut theorem, then loop for pairs of vertices and find the minimum cut for the tournament. i got it thanks $\endgroup$ – Prabu Sep 4 '10 at 16:14

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.