Ask Your Question
0

How to find a longest cycle and a longest induced cycle in a graph?

asked 2023-12-25 14:59:10 +0200

licheng gravatar image

updated 2023-12-25 15:00:44 +0200

Sage has longest_path. Do we have a command to find a longest cycle for a given graph? And an induced cycle is a cycle that is an induced subgraph of $G$; induced cycles are also called chordless cycles. Then do we have a function to find the longest induced cycle?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2023-12-25 18:38:15 +0200

Max Alekseyev gravatar image

updated 2023-12-26 12:50:36 +0200

To get longest cycle, you can run longest_path using each edge edndpoints as starting/ending vertices, and selecting the longest one among them. Once edge is processed it can be removed from the graph.

def longest_cycle(H):
    G = H.copy()
    C = Graph()
    while G.size() > C.size():
        e = next(G.edge_iterator(labels=False))
        P = G.longest_path(*e)
        if P.size() > 1:
            P.add_edge(e)
            if P.size() > C.size():
                C = P
        G.delete_edge(e)
    return C

To get a longest induced cycle, one can perform search for cycles of decreasing size as induced subgraphs:

def longest_induced_cycle(G):
    for n in range(G.order(),2,-1):
        H = G.subgraph_search(graphs.CycleGraph(n),induced=True)
        if H is not None:
            return H
    return Graph()

This approach can also be used to search non-induced cycles (by setting induced=False), but it will be slower than the one given above.

edit flag offensive delete link more

Comments

Sorry, I didn't understand the second one. What is the theoretical basis? By your codes, it seems that a graph with minimum degree $\ge 3$ does not contain induced cycles (as you delete all vertices). Did I misunderstand?

licheng gravatar imagelicheng ( 2023-12-26 08:50:02 +0200 )edit
1

@licheng: my mistake, corrected now.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-12-26 12:44:47 +0200 )edit
2

I proposed a more efficient method for both versions in #37028. It implements a integer linear programming formulation using constraints (cuts) generation. It's reasonably efficient for graphs with 50 nodes.

David Coudert gravatar imageDavid Coudert ( 2024-01-07 19:33:03 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-12-25 14:59:10 +0200

Seen: 329 times

Last updated: Dec 26 '23