Hi. I would like to work on this issue. I am already a bit familiar with igraph. This seems like a really interesting issue and I think I'll get to learn quite a lot about graph generation (theoretically and implementation-wise)!

Thank you for your interest in helping us develop igraph further! Here's a short guide for contributors that should help you get started:

https://github.com/igraph/igraph/wiki/Quickstart-for-new-contributors

I cannot emphasize enough that we really mean that you should start drafting a PR as soon as you are a bit familiar with the topic - it is easier for us to guide you along the way if you have an understanding of what you are working on and how you intend to tackle the problem. As @szhorvat suggested above in the text of the issue, work out the math first, and then feel free to start a PR.

Happy coding! :)

Thank you. After working out the maths part, I'll open a draft PR for the implementation.

Hi. I tried thinking of ways to generate kneser graphs more efficiently than the direct approach. I also tried searching for existing resources but I haven't made any headway in this.

I went through sage's kneser graph generator. They have used the direct approach as well.

def KneserGraph(n, k):
    # Initialise a graph structure
    g = Graph(name="Kneser graph with parameters {},{}".format(n, k))

    from sage.combinat.subset import Subsets

    # 'Subsets' uses itertools.combinations to generate subsets
    # Complexity: nCk
    S = Subsets(n, k)
    if 2 * k > n:
        g.add_vertices(S)

    s0 = S.underlying_set()    # {1,2,...,n}

    # Complexity of outer loop: nCk
    for s in S:
        # Complexity of inner loop: (n-k)Ck
        for t in Subsets(s0.difference(s), k):
            g.add_edge(s, t)

    return g

The time complexity is $$\binom{n}{k} \binom{n - k}{k}$$

Generally Sage is very good, so if they didn't find a better way, I think we can go ahead. It's always good to leave a comment in the code pointing out the bad complexity, in case someone comes up with a better idea in the future.

I think we can go ahead

Alright, in that case I'll open a draft PR and will start working on it. As pointed out in the first comment, I'll start with the subset generation iterator.

It's always good to leave a comment in the code pointing out the bad complexity, in case someone comes up with a better idea in the future.

Sure, I'll do that.

What are the constraints on n and k going to be like?

Sounds good. Just letting you know that there are a number of outstanding PRs from people working on other projects, so it may take a while before we get the chance to look at yours.

If using the direct implementation, first implement a k-subset iterator.

Hi. Sorry for the inactivity. By iterator, are you referring to something similar to vertex iterators such as igraph_vit_t or just a function that generates $\binom{n}{k}$ subsets?