4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Feb 1 '16 at 21:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Boson
    Feb 1 '16 at 23:33
  • 1
    $\begingroup$ Ok, thanks, that answers that question. But again, what is the model of computing? $\endgroup$ Feb 1 '16 at 23:52
  • $\begingroup$ @DavidEppstein The graph is represented by an adjacency list. $\endgroup$
    – Yu-Han Lyu
    Feb 2 '16 at 0:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yu-Han Lyu
    Feb 3 '16 at 15:12
9
$\begingroup$

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.

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