### ayushmalik03's blog

By ayushmalik03, history, 2 months ago, ,

Problem A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes u and v (u ≠ v) exists either an edge going from u to v, or an edge from v to u. You are given a tournament consisting of n vertexes. Your task is to find there a cycle of length three.

n<=5000;

. Instead of 3 , if it was k than how should we approach this problem ?

• +2

 » 2 months ago, # |   0 Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 3 →   0 I smell NP hardness... Ok, maybe this problem is not NP-hard due to restriction to tournament graph. But I doubt that O(E) algorithm is possible.
 » 2 months ago, # | ← Rev. 13 →   +4 Here is a proof of polynomial time feasibility, though the runtime is probably suboptimal. (Contra the above poster, I think $O(E)$ is probably possible.)Recall a tournament of size $n$ contains a Hamilton cycle iff it is strongly connected. Hence we would like to find a strongly connected subtournament of size exactly $k$. Decompose the tournament into its strongly connected components and consider all components of size at least $k$. So we reduce to the case where we have a strongly connected tournament on $n \geq k$ vertices.For each component of size at least $k$, find a 3-cycle $C$ (since you are generalizing that problem I assume you know how to solve it). If there is a vertex with edges both into, and out of, our cycle $C$, we can add it to $C$ for free without affecting strong connectedness. If no such vertex exists, the remaining vertices separate into two sets $I, O$ such that all edges are oriented $I \to C\to O$, which implies we have at least one edge from $u\in O$ to $v\in I$, and we can freely add $u, v$ to $C$ while maintaining its strong connectedness.This all works out fine as long as $|C|\leq k-2$. The issue of course occurs when $|C|=k-1$ and we cannot find a single vertex to add. But by induction we can find a cycle of length $k-2$ in $C$ (which has size $k-1$) and then add two vertices to this cycle.The result is a strongly connected subtournament of size $k$ which must contain a Hamilton cycle.