#11735: Bug in is_chordal
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: tbd
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.2
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Nathann Cohen
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* cc: ddestrada (added)
Old description:
> As reported by Jan on sage-devel [1], the current implementation of
> is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y
> being non-adjacent), a shortest path between x and y in G-v does not
> necessarily avoid the neighbors of v. Clearly.
> Well, with this patch the shortest path is computed in the graph G with v
> and all its neighbors removed with the exception of x and y, so that it
> can not happen again.
>
> Besides, as it is almost free to check that the certificate is indeed a
> hole, this patch adds a test just in case `:-)`
>
> Nathann
>
> [1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion
New description:
As reported by Jan on sage-devel [1], the current implementation of
is_chordal is incorrect. Given a vertex v adjacent to x and y (x and y
being non-adjacent), a shortest path between x and y in G-v does not
necessarily avoid the neighbors of v. Clearly.
Well, with this patch the shortest path is computed in the graph G with v
and all its neighbors removed with the exception of x and y, so that it
can not happen again.
Besides, as it is almost free to check that the certificate is indeed a
hole, this patch adds a test just in case `:-)`
Nathann
Requires :
* #11738
Apply:
* [attachment:trac_11735.patch]
[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion
--
Comment:
As this patch is already written (and readily updated to be applied on top
of #11738), I think it best to merge it into Sage as soon as possible. It
(apparently) fixes the bug reported by Jan, but most importantly ensures
that the answer returned is indeed *valid*, so that no erroneous answer
could be returned as previously.
Of course, this version of the implementation will have to be patched as
soon as possible using Jan's code, in order to match a proven algorithm
(or until I can come up with a proof that the current implementation is
correct, or find a paper that does if I actually found it somewhere).
I'll do that *asap*, but I still think it better to merge this patch in
the meantime, if only to be sure no bad answer is ever returned (God I
hate that).
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11735#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
