2
$\begingroup$

This is an exercise from an old exam that I don't know how to solve.

For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a polynomial time algorithm which, for every graph $G$, returns some cycle in that graph which length is at least $\frac{c(G)}{2}$, then there exists a polynomial time algorithm which, for every graph $G$, returns some cycle in that graph which length is at least $\frac{c(G)}{\sqrt{2}}-1$

My solution attempt:
Let's name the algorithm from the problem statement $A$. Now I'm constructing algorithm $A'$. $A'$, when given graph $G=(V, E)$, first creates $G^2=(V^2, E')$, where $E'$ is defined as: for every $\{u,w\} \in E$, the following edges appear in $E'$:

  1. for every $x \in V$ $\{(x, u), (x, w)\} \in E'$ ($x$ here represents one of the copies of original $G$)
  2. for every $x, y \in V$ $\{(u, x), (w, y)\} \in E'$ (this means all the copies of $G$ are connected with scheme "every vertex in one with every vertex in second")

Observation:

$c(G^2) \ge c(G)^2$

This is true because having some cycle in $G$, we can mimic such cycle going through the copies of $G$, so that we visit $c(G)$ vertices in $c(G)$ copies, amounting to $c(G)^2$ vertices in total.

Let $R$ be result of running $A$ on $G^2$. Now, we should probably extract somehow some cycles from $R$ that are easily embeddable into $G$ and argue somehow that the longest of those will be at least $[\frac{c(G)}{\sqrt{2}}]$.
One candidate (call it $C1$, is a cycle extracted from first component of vertices (as if we have shrunk all copies of $G$ into single vertices). If length of $C1$ is smaller than $[\frac{c(G)}{\sqrt{2}}]$, then in at least one of the copies of G, there are at least $\frac{c(G^2)}{2} / \frac{c(G)}{\sqrt{2}} \ge \frac{c(G)}{\sqrt{2}}$ vertices on the cycle (I'm a bit sloppy about the floor function here, I hope it doesn't make much difference).
Now, the problem is that in such one copy of $G$, the cycle can be fragmented into some number of disjoint paths, so it's not obvious how one could recover a proper cycle from that. If, for instance, the problem statement were asking about a clique of size at least something, then this solution would work, because we would be certain that such vertices in one copy of $G$ form a clique as well. In case of a cycle however, we don't have this nice "subgraph also is of the same kind" property.
So the question is:

Is it possible to alter the solution slightly to make it work for cycles?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.