<p>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 <span class="math-container">$v$</span>, and then for every edge <span class="math-container">$(a, b)$</span> not in the tree, if <span class="math-container">$lca(a, b)=v$</span>, consider it as the shortest cycle (its length being, of course, <span class="math-container">$dist(v, a) + dist(v, b) + 1$</span>).</p>

CC BY-SA 4.0
2023-05-03T16:59:26.147Z
2023-05-03T16:59:26.147Z
Sharp Edged
<p>Given a connected undirected graph with edges <span class="math-container">$E$</span> and verticies <span class="math-container">$V$</span> and a vertex <span class="math-container">$v \in V$</span>, find the length of the shortest cycle containing <span class="math-container">$v$</span>. The best I could do is <span class="math-container">$O(|E|*deg(v))$</span>, by trying to choose every edge connected to <span class="math-container">$v$</span> as the last edge of the cycle (you just remove that edge <span class="math-container">$(u, v)$</span>, run BFS from <span class="math-container">$v$</span>, and the shortest cycle ending with that edge is of length <span class="math-container">$dist(u, v) + 1$</span>). How could you solve this problem in <span class="math-container">$O(E)$</span>?</p>

CC BY-SA 4.0
2023-05-05T10:49:36.340Z
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 https://cstheory.stackexchange.com/tour for suggestions of other venues more appropriate for such questions)
J.y B.y
<graph-theory>
Finding the shortest cycle containing a vertex in a graph
Sharp Edged
# Finding the shortest cycle containing a vertex in a graph

(Asked by: username_0 on 2023-05-03)

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)$?

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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 https://cstheory.stackexchange.com/tour for suggestions of other venues more appropriate for such questions)  

---

## 1 answers

### Answer by username_0 on 2023-05-03. Score: 0

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$).


---

