Find groups of articulation points

Question

I have some undirected graph and I try to find articulation points. There is example

It has one articulation point - vertex #2.

But I also want to find #4 and #5 as articulation group points. Because joint removing of #4,#5 also cut graph into unconnected subgraphs. I imagine example graph as a 3 connected subgraphs.

How can I find specified cut-points?

Answer 1

One approach is to find "2-connected component"s of your graph.

A 2-connected graph is a graph which is connected and doesn't contain any articulation points.

Edges of any simple graph can be partitioned into some 2-connected subgraphs.

The first example:

In the above graph, following are the 2-connected components:

• 4–2 3–4 3–1 2–3 1–2
• 8–9
• 8–5 7–8 5–7
• 6–0 5–6 1–5 0–1
• 10–11

The second example:

Each color corresponds to a 2-connected component. Multi-colored vertices are cut vertices (articulation points) and thus belong to multiple 2-connected components.

I think each component is an answer to your question. You can use Tarjan algorithm to find these components. Its time complexity is O(|V| + |E|) or O(n + m).

time = 0
function DFS(vertex, adj[][], low[], disc[], parent[], visited[], V, stack)
    disc[vertex]=low[vertex]=time+1
    time = time + 1
    visited[vertex]=true
    child = 0
    for i = 0 to V
        if adj[vertex][i] == true
            if visited[i] == false
                child = child + 1
                push edge(u,v) to stack
                parent[i] = vertex
                DFS(i, adj, low, disc, visited, V, time, stack)
                low[vertex] = minimum(low[vertex], low[i])
                if parent[vertex] == nil AND child > 1
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
                if parent[vertex] != nil AND low[i] >= disc[vertex]
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
            else if parent[vertex] != i AND disc[i] < low[vertex]
                low[vertex] = disc[i]
                push edge(u,v) to stack

fuction biconnected_components(adj[][], V)
    for i = 0 to V
        if visited[i] == false
            DFS(i, adj, low, disc, parent, visited, V, time, stack)
            while stack is not empty
                print last element of stack
                pop from stack 

Sources:

https://www.geeksforgeeks.org/biconnected-components/

https://en.wikipedia.org/wiki/Biconnected_component

https://www.hackerearth.com/practice/algorithms/graphs/biconnected-components/tutorial/

Answer 2

I don't think there is any faster method other than loop through all combination as you don't have any restriction. (I even don't think this test is meaningful.)

Though programming language is not specified, please let me to use python as example.

When you are doing articulation points searching, the most well-known method is Tarjan’s algorithm. I think everyone reading this know it, so I will skip it as a function if you don't mind, where you can find in https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/.

class Graph:
   #From www.geeksforgeeks.org
def worker(g, prefix, arr, u):

    container = g.graph[u]
    if u in g.AP():
        print prefix
        arr.append([prefix])
        del g
    else:
        for i in container:
            if str(i) not in prefix.split(' '):
                new_prefix = prefix + ' ' + str(i)
                new_g = copy.deepcopy(g)
                new_g.combineNode(u, i)
                if len(new_g.graph) > 1:
                    worker(new_g, new_prefix, arr, i)

struct = {
    0:[1,12,13,14,15],
    1:[2,12,14,15],
    2:[3,4,5,14],
    3:[4],
    4:[5,6],
    5:[6,9],
    6:[7,8,9],
    7:[8,10,11],
    8:[9,10,11],
    9:[10],
    10:[11],
    12:[15],
    13:[14,15]
} 
g1 = Graph (total)

for key,value in struct.iteritems():
    for child in value:
        g1.addEdge(key, child)

result = []
for i in range(0, total):
    print 'Remove root ' + str(i)
    worker(g1, str(i), result, i)
print result

I write it in case that only the least length of group to divide the graph. As, lets say (4, 5), if it is already the AP, any points connect to them should be AP as well.

Just in case, anyone want the full Testing code. https://gist.github.com/MichaelKHTai/c438fd0911d0584be1e37f1fd1599b7e

Besides, it should be optimized by skipping duplicated group of nodes, like (4,5) and (5,4).