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

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).