For a certain strongly connected directed graph, i.e. a directed graph where every pair of vertices is connected by an arc, I am looking for a linear complexity algorithm which, by inputting the $\frac{n(n-1)}{2}$ pairs of vertices ordered by the orientation of their arc, can tell if there is a vertex $v$ such as $\delta^+(v) \leq 1$, where $\delta^+(v)$ denotes for the outdegree of $v$.

Obviously the naive algorithm exists, with a complexity $O(n^2)$, which looks at all pairs of vertices.

In the head, for cases where $n \leq 15$ I can figure it out with less than $5n$ steps, but I can't come up with an efficient linear complexity algorithm.

Examples with $n = 5$ :

no such vertex

There's one (vertex 3)

Is there such an algorithm?

  • $\begingroup$ In your “no such vertex” example, doesn’t $2$ have outdegree 1? $\endgroup$
    – Joppy
    Mar 30 '20 at 14:06
  • $\begingroup$ The other comment is that if the input is a list of ordered pairs, you cannot possibly have linear time since the list is quadratic length, and (at least it seems like) we will have to look through the whole thing, since the orientation of the very last edge might be the difference between such a vertex existing or not. $\endgroup$
    – Joppy
    Mar 30 '20 at 14:07
  • $\begingroup$ indeed there is a mistake in example 1 $\endgroup$ Mar 30 '20 at 14:20

Whether or not an $O(n)$ algorithm exists depends heavily on your computational model. (A single-tape Turing machine, for example, would take $O(n^2)$ time even to crawl to the end of the input to look at the edge between vertices $n-1$ and $n$.) But I can give you an algorithm that inspects fewer than $5n$ of the edges to find such a vertex.

Borrowing some language from tournament brackets, we say that vertices $v$ and $w$ "play" if we look at the edge $vw$, and a vertex $v$ "wins" against another vertex $w$ if the edge between them is oriented $w \to v$. As in a double-elimination tournament, two losses eliminate a vertex.

We begin by the following procedure: have vertices $1$ and $2$ play. Then the winner plays vertex $3$. The winner of that plays vertex $4$, and so on. After $n-1$ games, we end up with $n-1$ losers (which have outdegree $1$ already) and a winner.

We can sort the vertices into two groups as we do the procedure above. First put $1$ in group A and $2$ in group B. After that, whenever two vertices play, one of them already has a group, and we put the other vertex in the other group. The result is that the $n-1$ losers are separated into groups A and B, and no two vertices in the same group have played yet.

Repeat the procedure we did two more times. First, for group A (the first two vertices in the group play, then the winner plays the third vertex, and so on.) Second, for group B. This produces the "top A loser" and the "top B loser". Except for them, every vertex in group A or B has lost two games, so it has outdegree $\ge 2$ and is out of consideration.

We've played $2n-4$ games so far, and now there are only $3$ vertices remaining that could potentially have outdegree $1$ or less: the winner, the top A loser, and the top B loser. So, have each of them play every other vertex. This takes at most $3n$ more steps; realistically, it takes fewer, because some of those games have already been played. After fewer than $5n$ games total, we've either found a vertex with outdegree $\le 1$, or determined that all vertices have outdegree at least $2$.

  • $\begingroup$ In the part of the tournament that concerns the games between the losers in groups A and B, would there not be a total of $n-3$ games, which would make a total of $2n-4$ games at the end of the tournament? $\endgroup$ Mar 30 '20 at 15:22
  • $\begingroup$ Oh, good point. $\endgroup$ Mar 30 '20 at 16:01

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.