Dear All,
igraph can compute a fill-in necessary to make a graph chordal. I noticed that the fill-in it returns is usually far from optimal. While igraph makes no claims of generating a minimal fill-in, I do wonder if this behaviour is correct or if something is going wrong.
A simple example is a 2D grid graph, where a trivial minimal fill-in is adding the "diagonals" of each "square".
Example in R:
g <- make_lattice(c(2,3))
is_chordal(g, fillin=T)
The fill-in it returns is (6 3) (4 1) (6 1) (5 1). If you plot the graph, you'll see that (6 3) (4 1) is sufficient. For larger graphs the fill-in tends to be even more suboptimal.
So is this the expected behaviour?
Szabolcs