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()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])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).
@David Coudert Your idea is worth implementing in Sage.
This is now https://github.com/sagemath/sage/pull...
Asked: 0 years ago
Seen: 243 times
Last updated: Jul 22 '24
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
For each
graph, do you want to use your function for a singlesubsetor 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 aO(m)algorithm but running.is_cut_vertex(v)for each vertexvof the graph would beO(m^2).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.