# Does Sage have a function to determine vertex cuts?

I know about is_cut_vertex(G, u) for checking if a vertex is a cut-vertex. But is there a function in Sage to determine if a subset of vertices is a vertex cut? Although it's not too difficult to write, as shown below:

def is_vertex_cut(graph, subset):
subgraph = graph.copy()
subgraph.delete_vertices(subset)
return not subgraph.is_connected()

edit retag close merge delete

For each graph, do you want to use your function for a single subset or many? I ask because it might not be the most efficient for what you aim to do. For example, to compute the list of cut vertices there is a O(m) algorithm but running .is_cut_vertex(v) for each vertex v of the graph would be O(m^2).

( 2024-07-22 16:00:41 +0200 )edit

Thank you. I am not testing whether a set of vertices are cut vertices individually, but rather whether a subset of vertices forms a vertex cut set. Indeed, my goal is to test many subsets to determine whether they are vertex cut sets.

( 2024-07-23 05:29:59 +0200 )edit

Sort by ยป oldest newest most voted

Such function does not seem to exist. The most relevant page for such questions seems to be Connectivity related functions Alternatively, you could use the following

def is_vertex_cut_bis(graph, subset):
new_graph = graph.copy()
new_graph.merge_vertices(subset)
return new_graph.is_cut_vertex(subset[0])

more

2

The most efficient method is to do a depth-first search starting from a neighbor of subset, avoiding to visit vertices in subset. On the way, we record visited vertices. When it's done, it suffices to check if there is a vertex that has not be visited by the search and that is not in subset. This can be done in time O(n + m).

( 2024-07-22 19:03:03 +0200 )edit

@David Coudert Your idea is worth implementing in Sage.

( 2024-07-23 05:31:35 +0200 )edit
( 2024-07-24 18:33:17 +0200 )edit

@David Coundert Nice. A similar problem, I am not sure if there is an implementation for determining if a set of edges is a cut-set (removal results in disconnection of a graph).

( 2024-07-25 06:28:20 +0200 )edit