1
$\begingroup$

The problem I'm facing is the following:

Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$.

The algorithm I can think of is to remove an edge from $u$ to one of its neighbours $v$ at a time and ask if there is still a path from $u$ to $v$ in the resulting graph, placing $(u,v)$ back before the next iteration.

I estimate the time complexity as $O(\Delta\cdot(m+n))$, with $\Delta$ being the greatest degree of the graph and $(m+n)$ for using a BFS on each iterarion.

Is there a better algorithm than this one? Does a simple DFS solve this problem and I'm just losing time with this?

BFS: Breadth-First Search
DFS: Depth-First Seatch

Improve this question
$\endgroup$
3
  • $\begingroup$ I searched the site for an answer to this question, but couldn't find one (maybe the terms I used in the search weren't good...) $\endgroup$
    – araruna
    May 22 '15 at 17:51
  • $\begingroup$ When a vertex is on a cycle, it has two distinct neighbours on the same cycle (unless edges are not defined as pairs of vertices). $\endgroup$
    – babou
    May 22 '15 at 23:22
  • 2
    $\begingroup$ See this answer on Stack Overflow. $\endgroup$
    – David Richerby
    May 23 '15 at 6:13
2
$\begingroup$

You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.

Then you can check whether one neighbour can reach another.

Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).

I let you work out the details.

Improve this answer
$\endgroup$

Your Answer

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

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