# Polynomial time algorithms for graphs and cycles

For a given undirected graph $$G$$ , let $$c(G)$$ denote the length of the longest cycle in $$G$$ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time algorithm that, for every graph $$G$$, returns some cycle in this graph with length at least $$\frac{c(G)}{2}$$, then there also exists a polynomial-time algorithm that, for every graph $$G$$, returns some cycle in this graph with length at least $$\frac{c(G)}{\sqrt{2}}-1$$.

I think the idea is to modify the input graph and run the first algorithm on it. But I have no idea how exactly input should be modified... Where does $$\sqrt{2}$$ come from? Maybe graph product should be considered?

• Where did you encounter this task? Can you credit the original source?
– D.W.
Commented Jul 17 at 19:05
• @Minko_Minkov $\left\lfloor\frac{c(G)}{2}\right\rfloor$ is smaller than $\left\lfloor\frac{c(G)}{\sqrt{2}}\right\rfloor - 1$ when $c(G)\ge 9$. Commented Jul 19 at 14:42