I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:

  • remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
  • on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
  • take back the original graph and remove the cut vertex. Check the size of the largest connected component

This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...

  • 2
    $\begingroup$ Do you have any constraint on the size of the cut-vertex? Otherwise, the most trivial solution is to choose two leaf nodes (nodes with degree equal to $1$), and make other nodes cut-vertex. If you remove these vertices you will have two components of size $1$. The largest of these components is obviously has the size $1$ which is not greater than any threshold except $0$. $\endgroup$ – fade2black Nov 16 '17 at 10:03
  • $\begingroup$ You may want to read this. $\endgroup$ – Raphael Nov 16 '17 at 11:19
  • $\begingroup$ Have you tried proving your algorithm correct? An inductive proof seems prudent here. $\endgroup$ – Raphael Nov 16 '17 at 11:21
  • $\begingroup$ @Raphael - Thanks for the hint. Do you say this because you suspect the algorithm might not work? I am not really good at proofs, so any help on how to prove it would be really appreciated $\endgroup$ – Sean Nov 16 '17 at 16:07
  • $\begingroup$ I have not formed an opinion on your algorithm. My gut feeling is that linear time is not enough for an optimization problem like this, so if I were to ballpark-guess I'd say it's wrong. Then I'd try to find a counter-example. (Of course, it looks to me as if your algorithm takes quadratic time. ;) That may be feasible.) $\endgroup$ – Raphael Nov 16 '17 at 17:58

Given a graph $G$ and a threshold $k$, you are looking for an articulation point whose removal divides the graph into connected components all of size $\le k$. This can be done in linear time.

First, construct the block-cut tree of $G$. This is a tree $T$ that has one node for each biconnected component of $G$ and one node for each articulation point of $G$, with an edge between a biconnected component $c$ and an articulation point $a$ if $a$ is contained in $c$. The block-cut tree can be constructed in linear time.

Now you want to find an articulation node in the tree $T$ whose removal disconnects the tree into connected components all of size $\le k$. This can be done in linear time. In particular, the algorithm problem is the following:

Given a tree $T$ and a threshold tree, we are looking for a node in $T$ whose removal disconnects $T$ into connected components all of size $\le k$.

This can be done in linear time. You pick an arbitrary node to be the root of $T$. With a bottom-up traversal, you annotate each node with the number of descendants it has. Now if we focus on a single node, we can use the annotation on its neighbors to determine the size of all connected components that result if we delete that node, in time proportional to the number of neighbors it has. This lets you check whether deleting that node would leave you with connected components all of size $\le k$. So iterate over all nodes and check whether any qualifies. The total amount of work is proportional to the number of edges in the tree, which is proportional to the number of vertices in the tree.

Thus, the total running time is linear in the size of $G$.

  • $\begingroup$ Thank you very much! However I managed to do it without building the block-cut tree. Just traversing the tree and keeping track, for each node, of the size of the biggest connected component (this can be done just by looking at its neighbors). $\endgroup$ – Sean Nov 19 '17 at 23:31

Your algorithm may not work. What you describe, in fact, is an algorithm for computing the center of the tree. The following is a brief theory behind this algorithm.

The distance, denoted by $dist(v,u)$, between two vertices $u$ and $v$ is defined as the shortest path between $u$ and $v$. The eccentricity of a vertex $v$ is defined as $$ \epsilon(v)=\max_{u \in V}\{dist(v,u)\}$$ In simple words $\epsilon(v)$ is the maximum among all distances from the $v$ to a vertex $u$.

We define the center of a graph $G$ is the set of vertices with minimum eccentricity. Observe that step-by-step leaf removal in your algorithm does not change the eccentricity of the center.

Your algorithm essentially computes the center of the tree but the following is a counterexample. This tree

enter image description here

has the center $v_c$. Your algorithm will return $v_c$ as the cut vertex. But if your threshold is $3$ then the optimal cut vertex would be the vertex $u$.

  • $\begingroup$ You are right, then it's not going to work. Any other idea? I can't think of anything else $\endgroup$ – Sean Nov 16 '17 at 17:37

Your Answer

