Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

37 Views Asked by At

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear to me whether this task can be done in linear time. There are a variety of linear time algorithms for detecting things such as bridges, 3-connected components, and 3-edge-connected components, but as far as I can tell these algorithms do not directly translate into an algorithm for detecting 2-edge cuts.

I would greatly appreciate any insight into this problem, or any relevant research which I could be pointed towards.