Check if a graph admits a separating 3-cycle.

asked 2025-06-15 13:36:00 +0200

licheng
327 ●11 ●29 ●46

updated 2025-06-15 13:36:43 +0200

We say that a 3-cycle is separating if its removal disconnects the graph. This function determines whether such a cycle exists.

def has_separating_3cycle(G):
    """
   Check if the graph admits a separating 3-cycle.
    """
    for S in Subsets(G.vertices(), 3):
        if G.subgraph(S).is_isomorphic(graphs.CompleteGraph(3)):
            H = G.copy()
            H.delete_vertices(list(S))
            if not H.is_connected():
                return True
    return False

I wrote the following function, but when I tested it on some graphs, it works reasonably well for graphs of around 50 vertices. However, is there a better way to write it for faster performance? I need to process around 25,000 graphs.

Comments

You can generate candidate cycles directly via G.to_directed().all_simple_cycles(max_length=3).

Max Alekseyev ( 2025-06-15 22:29:09 +0200 )edit

add a comment

answered 2025-06-16 07:55:53 +0200

David Coudert
851 ●13 ●21 http://www-sop.inria.f...

updated 2025-06-16 07:56:16 +0200

Use method atoms_and_clique_separators that returns a decomposition of the graph by clique minimal separators in polynomial time.

def has_separating_3cycle(G):
    cliques = G.atoms_and_clique_separators()[1]
    return any(len(c) == 3 for c in cliques)

edit flag offensive delete link

Comments

I'm still trying to understand this function. It seems to determine whether the graph contains a minimal k-separating clique? If our graph is already 3-connected, that would be especially great (which happens to be the case for my graphs). But if the connectivity is slightly lower, problems might arise. For example, G=Graph([(1,2),(2,3),(3,1),(1,4),(1,5),(2,6),(2,7)]) 1231 is a separating 3-cycle but the funtion gives me False, since it is not minimal(I guess).

licheng ( 2025-06-17 13:37:45 +0200 )edit

Right. method atoms_and_clique_separators returns the minimal clique separators. In your graph, clique {1, 2, 3} is not a minimal separator. If you want separators that are not minimal, you can elaborate on the idea proposed by Max Aleksyev:

def has_separating_3cycle(G):
    cycles = set(frozenset(c) for c in G.to_directed().all_simple_cycles(max_length=3) if len(c) == 4)
    for c in cycles:
        if not G.is_connected(forbidden_vertices=c):
            return True
    return False

David Coudert ( 2025-06-18 09:44:35 +0200 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Check if a graph admits a separating 3-cycle.

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Check if a graph admits a separating 3-cycle. edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Check if a graph admits a separating 3-cycle.