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

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 close merge delete

Sort by ยป oldest newest most voted

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

more

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?

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

@licheng: my mistake, corrected now.

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

( 2024-01-07 19:33:03 +0200 )edit