0
$\begingroup$

Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to choose every edge connected to $v$ as the last edge of the cycle (you just remove that edge $(u, v)$, run BFS from $v$, and the shortest cycle ending with that edge is of length $dist(u, v) + 1$). How could you solve this problem in $O(E)$?

$\endgroup$
1
  • 2
    $\begingroup$ Could you share more about the background in which you want this question answered? With such a broad settings, people might wonder if this is merely a homework assignment, for which cstheory.stackexchange is not the right venue (see cstheory.stackexchange.com/tour for suggestions of other venues more appropriate for such questions) $\endgroup$
    – J..y B..y
    May 5, 2023 at 10:49

1 Answer 1

0
$\begingroup$

Ok, seems the problem is actually pretty easy. Just make the BFS tree (or shortest path tree in case of a weighted graph) rooted at $v$, and then for every edge $(a, b)$ not in the tree, if $lca(a, b)=v$, consider it as the shortest cycle (its length being, of course, $dist(v, a) + dist(v, b) + 1$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.