Re: [igraph] Why are chordal completions computed by igraph so suboptimal?

[Tamas Nepusz]

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 <address@hidden> 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
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>