[Problem suggestion] Chordal graph recognition

[dragonslayerintraining]

Given an undirected graph with n vertices and m edges, determine if it is chordal.
If so, find a perfect elimination ordering.
If not, find an induced cycle of at least 4 vertices.

1<=n,m<=200000
Time limit: 5 seconds

I think the following is true (Please check. The resources I found on this problem don't explain how to efficiently find the cycle):
Let v_1, v_2, ... v_n be the vertices in the order found by maximum cardinality search (MCS).
The reverse of this ordering is a perfect elimination ordering if and only if the graph is chordal.
Otherwise, there exists i<j<k such that v_i and v_j are neighbors of v_k but v_i and v_j are not adjacent. There must exist some l<j such that v_l is adjacent to v_j but not v_k (since MCS picked v_j instead of v_k) If v_i and v_l are adjacent, we found a cycle. Otherwise, repeat the argument to extend the path with a vertex not adjacent to v_k. Eventually we get a cycle containing these three vertices and other vertices not adjacent to v_k. The shortest such cycle is an induced cycle of at least $4$ vertices. The final algorithm is O(nlogn) or O(n).

[yosupo06]

Thanks!

Your algorithm seems correct for me.

[bqi343]

@dragonslayerintraining Could you elaborate on "repeat[ing] the argument to extend the path with a vertex not adjacent to v_k." What vertex are you using to extend the path (i or j or l)?

There must exist some l<j such that v_l is adjacent to v_j but not v_k (since MCS picked v_j instead of v_k)

This is the case because we know that v_i is connected to v_k but not to v_j. If l<i then is it always true that there exists some m<i such that (v_m,v_i) exists but (v_m,v_k) doesn't?

Also, the perfect elimination ordering should have $N$ vertices, not $N+1$.

[dragonslayerintraining]

@bqi343 You're right. I didn't realize that. Maybe you could understand the proof here (I didn't).
Now I'm not sure if my approach to constructing a cycle is correct.

The $v_N$ is indeed a typo.