ayushmalik03's blog

By ayushmalik03, history, 7 months ago, In English

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 ?

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ayushmalik03 (previous revision, new revision, compare).

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 13   Vote: I like it +4 Vote: I do not like it

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.