Is there a way to compute the number of chordless cycles in a given graph with `igraph`

(in particular with the C library) ?

There are ways you can use, but they will be slow.

Take a look at `igraph_subisomorphic_lad()`

. It has an option to find only *induced* subgraphs. You can then look for induced (i.e. chordless) cycles for each size one by one. Note that this function computes subgraph isomorphsms, not subgraphs. There are 2n ways to map an n-cycle onto itself (n rotations and a reversal). Thus, the counts for n-cycles need to be divided by 2n.

Also look at `igraph_motifs_randesu()`

. This functions counts “motifs”, i.e. connected induced subgraphs of a given size. It is implemented only for size-3 and size-4 motifs, but it will be the fastest way to count size-4 induced cycles.

I don’t recall any other simple way using existing functions.

If you are aware of good algorithms for solving this problem, please open a feature request and provide referenced along with a brief summary of the topic.

Some relevant links:

https://link.springer.com/chapter/10.1007/978-3-319-11812-3_27

(Peer reviewed version of the above.)

(Did not find a peer-reviewed version.)

(It might be good to look at, but do not trust StackOverflow on topics like this one.)

For now it sounds heavy indeed.

EFFICIENT PARALLEL ALGORITHMS FOR FINDING CHORDLESS CYCLES IN GRAPHS

http://research.nii.ac.jp/~uno/code/cypath.html

http://research.nii.ac.jp/~uno/codes.htm

Are you feeling up to implementing an algorithm for this?

Thanks, I added it to the feature request issue.

Can you comment on the use cases, so we can fill that section out as well (see issue on GitHub)?