I'm not that familiar with this part of the library (it was added by Gabor I think), but I have read the original Tarjan & Yannakakis paper (on which the maximum cardinality search algorithm in igraph is based) and it says nothing about the fill-in set being minimal. I think the intention of the implementation in igraph was to return the fill-in set as reported by the Tarjan & Yannakakis algorithm but not to strive for the minimum fill-in set.
T. T. On Tue, Sep 22, 2015 at 8:27 PM, Szabolcs Horvát <[email protected]> wrote: > 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 > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
