6

In a tournament graph, how do I find whether there is a player who has dominated all the other players? What is the run-time of such algorithm?

Basically, I need to find if there is an element, from which I can reach to all the other elements, following the path of outlinks.

Clarification: Here; if 'a' beats 'b', and 'b' beats 'c', then a has dominated 'c'. Basically if 'a' beats 'c' directly OR indirectly, it has dominated 'c'. It might be possible that 'a' and 'b' have dominated each other indirectly, which is why the winner may or may not exist. There could also be more than one winners.

Tournament graph is a directed graph where each element has a directed edge with each of the rest of the elements. So there are n*(n-1)/2 directed edges, where n is the number of vertices(players). Wikipedia article on Tournament Graph

5
  • So the "winner" is the guy who dominated the most players? Apr 12, 2015 at 15:29
  • @ThomasJungblut Winner is the guy who has dominated all the players. I want to find if there is such a player in the tournament; if so, who he is.
    – dc95
    Apr 12, 2015 at 15:31
  • So if there is an edge from A to B when A wins over B, then you can simply count the outlinks from A and check whether it is equal to the number of vertices |V|-1. Or am I missing anything? Apr 12, 2015 at 15:33
  • @ThomasJungblut A could also dominate B indirectly. Say, A beats C, C beats D and D beats B. Basically I want to find the element, from which I can reach all the other elements (going through the path of outlinks). I will update the question.
    – dc95
    Apr 12, 2015 at 15:35
  • @DarshilChauhan In that case, I believe you can first compute the strongly connected components of the graph (that is, the condensation, and let's call it G). If there's only 1 vertex in G with in-degree equal to 0 and it consists of a single vertex in the original (uncondensed) graph, then this vertex is the one who dominates the rest. The order of the algorithm is the order of finding the condensation (which can be computed in O(V+E)). In the general case, if there's only 1 vertex with in-degree equal to 0 in G, you can reach all the other vertices in the original graph from there.
    – ale64bit
    Apr 12, 2015 at 15:39

3 Answers 3

5

Let's call the original graph T with N vertices and M edges. First compute the condensation of T and let's call it G. Every vertex v of G represents several vertices of T; additionally, you can reach from any of this vertices to another in T. Also, G is a DAG. So, if there's only one vertex in G with in-degree equal to 0 (let's call it v0), that means that you can reach any vertex in the original graph starting from a vertex in v0. If v0 corresponds to a single vertex in T, then it is the vertex you are looking for already. The complexity is O(N+M).

2
  • I understand what your are saying. But being new, I am having problem with implementing a condensation algorithm. Could you give me some resources on that? Or maybe write some code? I am trying to code by reading Wikipedia article on Kosaraju's algorithm because I read that it is the simplest.
    – dc95
    Apr 12, 2015 at 21:11
  • For finding the strongly connected components, you can do the following: 1) run DFS on T and compute the finishing time f(u) for every vertex u, 2) run DFS on T' (that is, the transpose of T, which is just reversing the edges) but consider the vertices in the order of decreasing f(u) and 3) output the vertices of each tree of the DFS in (2) as a separate strongly connected component. For more info, see Introduction to Algorithms or some other nice reference on graph algorithms.
    – ale64bit
    Apr 12, 2015 at 22:06
2

One way to do it is to take every vertice, and depth search the graph with that vertice as the root. For every depth search you check if you have visited every other vertices. If it has, the player which corresponds to that vertice dominates all the players in the graph. If you are familiar with C++ , I can write the program here. The time complexity is ~ O(N^3). Do you need a faster algorithm? N being the number of vertices

1
  • Wouldn't that make it O(N^3) complexity? Run-time of DFS is already O(V+E) = O(N^2 + N) = O(N^2). If you do it for all the elements then it becomes O(N^3). I want a solution in O(N^2).
    – dc95
    Apr 12, 2015 at 20:39
1

If there's a player who has dominated everyone else, then there exists exactly one vertex v in the graph with no incoming edges. Do a DFS starting from v. If you can reach every other vertex, then v is the dominating vertex.

EDIT 1: As kaktusito suggested, we could condense the graph before applying DFS.

EDIT 2: It looks like there's no need to explicitly compute all the connected components, apply condensation, construct DAG and find the dominating vertices. Instead here's a simpler solution:

First perform a DFS on the graph and find the node v with the highest finish time. If the graph has winners, then v has to be among them. Otherwise there would have been another vertex u such that v is reachable from u and which has a later finish time. Now to find other winners, find all nodes that are reachable from v in the transposed graph, using a DFS or BFS from v. The complexity of this algorithm is still O(V+E), but the implementation (and the constant) is substantially simpler.

7
  • That would make it O(N^3) complexity. Run-time of DFS is already O(V+E) = O(N^2 + N) = O(N^2). If you do it for all the elements then it becomes O(N^3). Is there a solution in O(N^2)?
    – dc95
    Apr 12, 2015 at 20:40
  • You don't need to do it for all elements. Since you want to find the player who has dominated everyone else, you only need to look at vertices whose in-degree is 0. Moreover, if there exists more than one such vertex, then we know no player has completely dominated every other. So if a solution exists, there should be exactly one vertex v which as indegree 0 and from which we can reach every other vertex. So we only need to do a single DFS from v.
    – krjampani
    Apr 12, 2015 at 20:48
  • 1
    Suppose A beats B, B beats C and C beats A. In that case none of them have in-degree 0, but all three of them are winners since one can reach other two from any one of the elements. I think what you are saying would be true only after condensation of the graph has been done. After condensation, the graph would be acyclic.
    – dc95
    Apr 12, 2015 at 20:57
  • I misinterpreted the question since I thought there would be no winner in that case. You are right, we need to run DFS on the condensed graph then.
    – krjampani
    Apr 12, 2015 at 21:13
  • I am having problem with implementing a condensation algorithm. Could you give me some resources on that?
    – dc95
    Apr 12, 2015 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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