$2$ All$-$Stars

Suppose you$$re organizing a tennis tournament between n players which we simply label as $1,2,...,$ n$.$ Each

player competes against every other player, and there are no repeat matches and no tied scores. We model

the results of the competition as a directed graph with n vertices and exactly one directed edge between

each pair of vertices: G $=($V$,$ E$),$ with V $=\{1,2,...,$ n$\}$ where either $($i$,$ j$))$ in E $($if i defeated j$),$ or

$($j$,$ i$))$ in E $($if j defeated i$).$ Such a graph is called a tournament.

You want to determine a way to rank these players, but a challenge here is that cycles may exist in

your tournament $$ e$.$g$.,$ i may defeat j in a match, and j could defeat k$,$ but then we could still have k win

a match against i; this would lead to a cycle of length three.

A ranking for the tournament is an ordering $($r$1,$ r$2,...,$ rn$)$ where node r$1$ is established as the overall

rank $1$ player. Due to the potential existence of cycles it is challenging to find a fair ranking.

$1.[4$ points$]$ We decide that the top ranked player should always be some node whose out$-$degree in the

directed graph is maximum. We motivate this claim by proving that if player i has maximum degree,

then for every other player j either i beat j$,$ or i beat some player k which beat j$.$ Prove this claim.

Hint: A proof by induction on n works well.

$2.[2$ points$]$ We decide that a reasonable definition is suggested by the previous result. A sequence of

nodes $($r$1,$ r$2,...,$ rn$)$ is a valid ranking if for each i $=1,2,...,$ n the node ri has maximum out$-$degree

in the sub$-$tournament induced by the nodes ri

$,$ ri$+1,...,$ rn$.$ Give a polynomial$-$time algorithm which

decides if a given permutation of the nodes $($v$1,$ v$2,...,$ vn$)$ is a valid ranking.

$3.[2$ points$]$ Describe a tournament of size n which has precisely one valid ranking.

$4.[4$ points$]$ One brute force method for producing all valid rankings is to consider all permutations of

the nodes and then use your algorithm for Part b to check each one if it is a valid ranking. This will

run in time O$($n$!$p$($n$))$ where p$($n$)$ is the runtime of your algorithm in Part b$.$

Instead, create a better algorithm which runs in time O$(|$V al$|$poly$($n$))$ where V al is the set of valid

rankings, and poly$($n$)$ is a polynomial in n$.($You do not need to analyze the runtime of your algorithm.$)$