<p>It's not possible for a deterministic algorithm: an adversary can always either fool the algorithm or make it look at $\Omega(n^2)$ entries of the adjacency lists.</p>

<p>Let $H$ be a disjoint union of two $n/4$-regular complete bipartite graphs. The adversary will remove a path of three vertices (not revealed to the algorithm) from each of the two components of $H$, and then replace these four removed edges by a different four edges that reconnect the two components, preserving $n/4$-regularity. It can do this in either of two ways:</p>

<ul>
<li>Swapping the middle vertices of each path results in a graph $H'$ with no non-cut vertices.</li>
<li>Replacing one path by an edge connecting its endpoints, and splicing its former middle vertex into the interior of the other path, results in a graph $H''$ with one cut vertex. The cut vertex can be made to be either of the two former middle vertices.</li>
</ul>

<p>However, by employing the strategy of making the removed path be in the last place the deterministic algorithm will look for it, it can force the algorithm to either not find the path (and not be able to distinguiish $H'$ from $H''$) or examine $\Omega(n^2)$ edges of the graph. In particular, as long as it is possible to answer a query (what is the $i$th entry of the adjacency list for vertex $v$) consistently with $H$, the adversary does so. Once the adversary is forced to choose the remaining path edges, it makes this choice arbitrarily, along with the choice of $H'$ or $H''$, and then answers the remaining queries according to the choice it made.</p>

<p>In order to force the adversary to choose between $H'$ or $H''$, the deterministic algorithm must see a set of edges that covers all two-edge paths on at least one of the two components on $H$. But each component of $H$ has $\Omega(n^2)$ disjoint two-edge paths, so the deterministic algorithm must see $\Omega(n^2)$ edges before it covers them all. And if it doesn't force the adversary to choose, then it is unable to distinguish graphs that have a cut vertex from those that don't, or to tell which vertex is the cut vertex.</p>

CC BY-SA 3.0
2016-02-02T06:58:40.707Z
2016-02-02T06:58:40.707Z
David Eppstein
<p>Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a <em>cut vertex</em> if removing this vertex with its incident edges from $G$ makes the graph disconnected. Finding a cut-vertex can be done in linear time.</p>

<p>My question is as follows: is it possible to find a non-cut vertex in $O(|V|)$ time?</p>

<p>My idea is to find a spanning tree of $G$, since all leaves of the spanning tree are non-cut vertices. However, I cannot find a spanning tree in $O(|V|)$ time.</p>

<p>Although I can find a cycle in $O(V)$ time, finding a non-cut vertex in a cycle seems not obvious to me.</p>

<p>I am wondering whether this problem has been solved, and I would appreciate any pointers provided by anyone.</p>

CC BY-SA 3.0
2016-02-01T21:11:54.820Z
I'm confused by something in your question. Isn't every vertex of a simple cycle a non-cut vertex? Also, what is your model of computing that allows computation in time that doesn't depend on $E$? Are you only allowed to query adjacency between pairs of vertices, or can you list edges incident to a vertex?
David Eppstein
CC BY-SA 3.0
2016-02-01T23:33:36.510Z
@DavidEppstein Pick the graph defined by $a \leftrightarrow b \leftrightarrow c \leftrightarrow d$ and $b \leftrightarrow e \leftrightarrow c$.
$c$ is a vertex of the cycle $(a,b,c)$, but removing it disconnects the graph: $a$, $b$ and $e$ on one hand and $d$ alone.
Boson
CC BY-SA 3.0
2016-02-01T23:52:13.913Z
Ok, thanks, that answers that question. But again, what is the model of computing?
David Eppstein
CC BY-SA 3.0
2016-02-02T00:47:58.617Z
@DavidEppstein The graph is represented by an adjacency list.
Yu-Han Lyu
CC BY-SA 3.0
2016-02-03T00:16:39.950Z
Even a simple DFS is O (E+V), what is the algorithm which runs in O(V) and finds the cut vertex (es)?
Saeed
CC BY-SA 3.0
2016-02-03T15:12:05.907Z
I didn't say finding a cut vertex can be done in $O(|V|)$ time. A cut vertex can be found in linear, $O(|V| + |E|)$, time.
Yu-Han Lyu
<graph-algorithms>
Is it possible to find a non-cut vertex in O(|V|) time?
Yu-Han Lyu
# Is it possible to find a non-cut vertex in O(|V|) time?

(Asked by: username_0 on 2016-02-01)

Let $G = (V, E)$ be an undirected connected graph, which is represented by an adjacency list. A vertex is called a *cut vertex* if removing this vertex with its incident edges from $G$ makes the graph disconnected. Finding a cut-vertex can be done in linear time.

My question is as follows: is it possible to find a non-cut vertex in $O(|V|)$ time?

My idea is to find a spanning tree of $G$, since all leaves of the spanning tree are non-cut vertices. However, I cannot find a spanning tree in $O(|V|)$ time.

Although I can find a cycle in $O(V)$ time, finding a non-cut vertex in a cycle seems not obvious to me.

I am wondering whether this problem has been solved, and I would appreciate any pointers provided by anyone.

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: I'm confused by something in your question. Isn't every vertex of a simple cycle a non-cut vertex? Also, what is your model of computing that allows computation in time that doesn't depend on $E$? Are you only allowed to query adjacency between pairs of vertices, or can you list edges incident to a vertex?  
> **username_2**: @DavidEppstein Pick the graph defined by $a \leftrightarrow b \leftrightarrow c \leftrightarrow d$ and $b \leftrightarrow e \leftrightarrow c$. $c$ is a vertex of the cycle $(a,b,c)$, but removing it disconnects the graph: $a$, $b$ and $e$ on one hand and $d$ alone.  
> **username_1**: Ok, thanks, that answers that question. But again, what is the model of computing?  
> **username_0**: @DavidEppstein The graph is represented by an adjacency list.  
> **username_3**: Even a simple DFS is O (E+V), what is the algorithm which runs in O(V) and finds the cut vertex (es)?  
> **username_0**: I didn't say finding a cut vertex can be done in $O(|V|)$ time. A cut vertex can be found in linear, $O(|V| + |E|)$, time.  

---

## 1 answers

### Answer by username_1 on 2016-02-02. Score: 9 | Accepted answer

It's not possible for a deterministic algorithm: an adversary can always either fool the algorithm or make it look at $\Omega(n^2)$ entries of the adjacency lists.

Let $H$ be a disjoint union of two $n/4$-regular complete bipartite graphs. The adversary will remove a path of three vertices (not revealed to the algorithm) from each of the two components of $H$, and then replace these four removed edges by a different four edges that reconnect the two components, preserving $n/4$-regularity. It can do this in either of two ways:

* Swapping the middle vertices of each path results in a graph $H'$ with no non-cut vertices.
* Replacing one path by an edge connecting its endpoints, and splicing its former middle vertex into the interior of the other path, results in a graph $H''$ with one cut vertex. The cut vertex can be made to be either of the two former middle vertices.

However, by employing the strategy of making the removed path be in the last place the deterministic algorithm will look for it, it can force the algorithm to either not find the path (and not be able to distinguiish $H'$ from $H''$) or examine $\Omega(n^2)$ edges of the graph. In particular, as long as it is possible to answer a query (what is the $i$th entry of the adjacency list for vertex $v$) consistently with $H$, the adversary does so. Once the adversary is forced to choose the remaining path edges, it makes this choice arbitrarily, along with the choice of $H'$ or $H''$, and then answers the remaining queries according to the choice it made.

In order to force the adversary to choose between $H'$ or $H''$, the deterministic algorithm must see a set of edges that covers all two-edge paths on at least one of the two components on $H$. But each component of $H$ has $\Omega(n^2)$ disjoint two-edge paths, so the deterministic algorithm must see $\Omega(n^2)$ edges before it covers them all. And if it doesn't force the adversary to choose, then it is unable to distinguish graphs that have a cut vertex from those that don't, or to tell which vertex is the cut vertex.


---

