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 ?
Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).
Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).
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.