How to maximize the number of connected components of a graph by removing an articulation point

Question

I am interested in the following problem : let $G=(V,E)$ be a connected graph. I would like to disconnect the graph by removing a vertex (an articulation point), such that the resulting number of connected components is maximized.

A dirty algorithm would be to iteratively remove each vertex and count the resulting number of components.

I would prefer doing this with a MIP. For this I need a condition that ensures disconnectedness.

Any help is welcome. Thanks.

Answer 1

Let $x_{ij}=1$ if vertex $i$ is in component $j$. For each edge $\{i_1,i_2\} \in E$ you add a constraint that the vertices $i_1$ and $i_2$ have to be in the same component: $x_{i_1,j} = x_{i_2,j}$. Let $y_i$ be the vertex that gets removed. If you rewrite the previous equality constraint as two inequalities, they become $x_{i_1,j} \leq x_{i_2,j} + y_{i_1} + y_{i_2}$ and $x_{i_1,j} \geq x_{i_2,j} - y_{i_1} - y_{i_2}$, so that the inequalities are always satisfied if either $y_{i_1}$ or $y_{i_2}$ is $1$. Lastly, add a binary variable $z_j$ to indicate if component $j$ is contains a vertex: $z_j \leq \sum_i x_{ij}$.

The full problem becomes: $$\begin{align} \max \quad & \sum_j z_j \\ \text{s.t.} \quad & x_{i_1,j} \leq x_{i_2,j} + y_{i_1} + y_{i_2} \quad \forall \{i_1,i_2\} \in E \; \forall j \\ & x_{i_1,j} \geq x_{i_2,j} - y_{i_1} - y_{i_2} \quad \forall \{i_1,i_2\} \in E \; \forall j\\ &\sum_j x_{ij} = 1 \quad \forall i\\ &\sum_i y_i = 1 \\ &z_j \leq \sum_i x_{ij} \quad \forall j \\ &x,y,z \text{ binary.} \end{align}$$ You can start with a set for $j$ of small cardinality, and gradually increase the cardinality until the optimal value is less than the cardinality. In the optimal solution, one $j$ is used for the removed vertex, so the answer is one less than the optimal value.

Answer 2

Tarjan's algorithm helps to find all the articulation points in the graph and by doing some modifications in the algorithm we will be able to find out how many disconnected components will be left if we are to remove that vertex.

Modification: While applying Tarjan's Algorithm for every vertex maintain a count of child nodes which does not have a link-back to any ancestor of the current vertex. This count will denote the number of disconnected components formed if we remove the current vertex.

Algorithm:

While applying a simple DFS traversal, if we are at:

1. Root vertex: Count the number of child vertices which are needed to be visited separately.

2. Any other vertex: Count the number of child vertices which are not yet to be visited and after visiting in DFS traversal, has a low- link value greater than or equal to the discovery-time of the parent vertex (i.e. doesn't have any link with the ancestor of current vertex) and add one (for the component which contains ancestors of current vertex.

This count is equal to the number of disconnected components formed after removing that vertex.

Just remove the vertex having highest count.

Time Complexity would be O(V+E), where V is the number of Vertices and E is the number of Edges.

discoveryTime[node] = time++;            // discovery time of the node
lowLink[node] = discoveryTime[node];    
countLowValues = 0;
countChildren = 0;

for(auto childNode: adjList[node]){
    if(childNode == parent){continue;}

    if(discoveryTime[childNode] == -1){
        countChildren++;
        dfsTravel(childNode);
        if(lowLink[childNode] >= discoveryTime[node]){
            countLowValues++;
        }
    }
    
    lowLink[node] = min(lowLink[node], lowLink[childNode]);
}

if(parent == -1){
    disconnectedComponentsCreated[node] = countChildren;   // root node
}
else{
    disconnectedComponentsCreated[node] = countLowValues +1;  // normal node
}

A question I found related to this concept: link