IMO before exposing this, it makes sense to at least think about what API to use for the rest of the related functionality. Ideally, all related functionality should be exposed at the same time.

igraph_is_chordal does two things: (1) it decides if the graph is chordal and (2) it computes a chordal completion. IMO these can be exposed as two separate functions. I suggest chordal_completion() as the name of the second function. It will return a list of vertex pairs (edges).

When exposing a single C function as two high-level functions, a common concern is: will this lead to inefficiency by forcing users to run the same algorithm twice to get all pieces of information? This is not the case here, as the result of chordal_completion() already shows whether the graph is chordal.

The other related piece is igraph_maximum_cardinality_search(). This function is used internally by is_chordal(). If the user has already run maximum_cardinality_search(), it is possible to pass its result to is_chordal() directly, and avoid a second run of maximum_cardinality_search() when one also needs chordality computations.

What I do not have the answer to is: What happens if the result passed to igraph_is_chordal() is invalid? Hopefully it just returns a wrong result, but it does not crash.

IMO the priority list for exposing functionality is:

1. is_chordal()
2. chordal_completion()
3. maximum_cardinality_search()
4. re-using the result of maximum_cardinality_search() in is_chordal() or chordal_completion()

I would suggest doing (1) and (2) together (I disagree that (1) alone serves most needs). (3) is nice to include and (4) is low priority.

Thanks for the comments. I don't have time to implement 2+ now, so feel free to take over the PR if you think that's necessary.

With my current schedule in mind, I recommend merging as is and delaying 2+ for a later PR, unless @szhorvat has time to take over this PR right now...

I don't have time either.

If it will be just this single function in the next release, I suggest marking it as experimental for now, which means "We reserve the right to change this API" (hopefully we won't, but just in case).

FYI, I plan to implement chordal_completion() and the other suggestions as part of this PR (I'll just start pushing commits to this).

Thank you, that's great

I think everything that has been mentioned above is now implemented in this PR, along with tests. I'll wait for the CI to see if there are any outstanding issues.

I would like to suggest mentioning in the docs that the chordal completion that this function generates is not necessary minimal.

https://lists.nongnu.org/archive/html/igraph-help/2015-09/msg00088.html

I will review the docs for this functionality in the C core before 0.9.5 comes out.

Good point, I'll add a short note about that in the Python interface, but maybe it's worth elaborating on it further in the C core.

AFAIK the minimum chordal completion is NP-complete (Yannakakis, 1981). However, I was wondering whether we could at least guarantee that igraph returns a minimal chordal completion (i.e. one that is no longer a chordal completion if you remove at least one of its edges). The example mentioned on the mailing list is definitely not minimal.

This PR was also backported to master in 25e4f2e