amount of chordless cycles

Usage
1

Is there a way to compute the number of chordless cycles in a given graph with igraph (in particular with the C library) ?

2

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.

3

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

4

For now it sounds heavy indeed.

5

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

6

Are you feeling up to implementing an algorithm for this?

7
8

Amortized Õ(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graph

9

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)?