Sage: Ticket #11735: Bug in is_chordal
https://trac.sagemath.org/ticket/11735
<p>
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.
</p>
<p>
Besides, as it is almost free to check that the certificate is indeed a hole, this patch adds a test just in case <code>:-)</code>
</p>
<p>
Nathann
</p>
<p>
Requires :
</p>
<ul><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/11738" title="defect: Various issues in is_interval and is_chordal (closed: fixed)">#11738</a>
</li></ul><p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11735/trac_11735.patch" title="Attachment 'trac_11735.patch' in Ticket #11735">trac_11735.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11735/trac_11735.patch" title="Download"></a>
</li></ul><p>
[1] <a class="ext-link" href="https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11735
Trac 1.1.6ncohenWed, 24 Aug 2011 09:01:50 GMTstatus, component, description changed
https://trac.sagemath.org/ticket/11735#comment:1
https://trac.sagemath.org/ticket/11735#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>graph theory</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11735?action=diff&version=1">diff</a>)
</li>
</ul>
TicketncohenSat, 10 Sep 2011 16:17:00 GMTcc, description changed
https://trac.sagemath.org/ticket/11735#comment:2
https://trac.sagemath.org/ticket/11735#comment:2
<ul>
<li><strong>cc</strong>
<em>ddestrada</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11735?action=diff&version=2">diff</a>)
</li>
</ul>
<p>
As this patch is already written (and readily updated to be applied on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/11738" title="defect: Various issues in is_interval and is_chordal (closed: fixed)">#11738</a>), 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.
</p>
<p>
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).
</p>
<p>
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).
</p>
<p>
Nathann
</p>
TicketncohenSat, 10 Sep 2011 16:17:27 GMTattachment set
https://trac.sagemath.org/ticket/11735
https://trac.sagemath.org/ticket/11735
<ul>
<li><strong>attachment</strong>
set to <em>trac_11735.patch</em>
</li>
</ul>
TicketncohenTue, 06 Dec 2011 14:49:06 GMTcc changed
https://trac.sagemath.org/ticket/11735#comment:3
https://trac.sagemath.org/ticket/11735#comment:3
<ul>
<li><strong>cc</strong>
<em>dcoudert</em> added
</li>
</ul>
<p>
(I was told that from this ticket's content, one could not really know whether the ticket really needed a review. The answer is : yes it does, the present ticket has to be merged into Sage to fix the bug, and is followd by <a class="closed ticket" href="https://trac.sagemath.org/ticket/11961" title="enhancement: Fixes a bug in is_chordal -- two algorithms (closed: fixed)">#11961</a>. I thought of updating the discussion, but forgot about the ticket itself <code>^^;</code>)
</p>
<p>
Nathann
</p>
TicketdsmTue, 06 Dec 2011 15:00:07 GMT
https://trac.sagemath.org/ticket/11735#comment:4
https://trac.sagemath.org/ticket/11735#comment:4
<p>
Are we lucky enough that these patches fix <a class="closed ticket" href="https://trac.sagemath.org/ticket/10899" title="defect: is_chordal can raise TypeError (closed: fixed)">#10899</a> en passant?
</p>
TicketncohenTue, 06 Dec 2011 15:03:16 GMT
https://trac.sagemath.org/ticket/11735#comment:5
https://trac.sagemath.org/ticket/11735#comment:5
<p>
No it should not <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertTue, 06 Dec 2011 21:18:08 GMTreviewer set
https://trac.sagemath.org/ticket/11735#comment:6
https://trac.sagemath.org/ticket/11735#comment:6
<ul>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
Either I don't understand the definition of chordal graphs, or the current implementation is still incorrect. I did the test with sage-4.8alpha3, so I assume I don't need to add patch 11738.
</p>
<pre class="wiki">sage: N = 50
sage: NN = 3*N
sage: L = [(3*i, (3*i+1) % NN) for i in xrange(N)] + [(3*i, (3*i+2)%NN) for i in xrange(N)] + [((3*i+1)%NN, (3*i+2)%NN) for i in xrange(N)]
sage: G=Graph()
sage: G.add_edges(L)
sage: G.is_chordal()
True
sage: G.add_edge(0,15)
sage: G.is_chordal()
True
sage: G.add_edge(0,25)
sage: G.is_chordal()
True
</pre><p>
So, what's wrong ?
</p>
<p>
David.
</p>
TicketdcoudertTue, 06 Dec 2011 21:30:37 GMT
https://trac.sagemath.org/ticket/11735#comment:7
https://trac.sagemath.org/ticket/11735#comment:7
<p>
OK, the previous example is not correct (long day). But that one should be correct. I want to create a cycle of triangles. This should be chordal...
</p>
<pre class="wiki">sage: N = 50
sage: NN = 2*N
sage: L = [(2*i, (2*i+1) % NN) for i in xrange(N)] + [(2*i, (2*i+2)%NN) for i in xrange(N)] + [((2*i+1)%NN, (2*i+2)%NN) for i in xrange(N)]
sage: G = Graph()
sage: G.add_edges(L)
sage: G.is_chordal()
False
</pre><p>
Nathann, am I right this time ?
D.
</p>
TicketncohenWed, 07 Dec 2011 09:15:08 GMT
https://trac.sagemath.org/ticket/11735#comment:8
https://trac.sagemath.org/ticket/11735#comment:8
<p>
Well, this graph clearly contains a long hole (induced cycle). Sage can find it too, with the "certificate" flag :
</p>
<pre class="wiki">sage: G.is_chordal(certificate = True)
(False, Subgraph of (): Graph on 50 vertices)
sage: G.is_chordal(certificate = True)[1].show()
</pre><p>
I mean, a graph is chordal if it contains an induced long cycle, and if you build a cycle of triangles it will of course contain a large induced cycle : the triangles offer no protection against that (just take two vertices that are very far away from each other, and compute a shortest path between them. As any shortest path, this path is induced, and the same way you can obtain an induced cycle).
</p>
<p>
Nathann
</p>
TicketdcoudertWed, 07 Dec 2011 10:12:06 GMTstatus changed
https://trac.sagemath.org/ticket/11735#comment:9
https://trac.sagemath.org/ticket/11735#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
You're right Nathann. I should not try a patch after a long day of work...
</p>
<p>
I did new tests this morning and the algorithm works fine.
I have no compilation error.
The doc is OK and includes the test of the patch (I don't if it's usual to let the patch number in the doc, but it has no consequences).
</p>
<p>
So I'm positive with this patch.
</p>
<p>
Thank you Nathann.
</p>
<p>
I hope someone will later be able to improve the running time of the algorithm. Current implementation is quite slow for an O(m) algorithm compared to other (nicely impleted) algorithms with higher complexity
</p>
<pre class="wiki">sage: G = graphs.RandomInterval(1000)
sage: G.num_edges()
319501
sage: %time G.is_chordal()
CPU times: user 24.83 s, sys: 0.05 s, total: 24.87 s
Wall time: 24.95 s
True
sage: %time G.diameter()
CPU times: user 1.59 s, sys: 0.00 s, total: 1.59 s
Wall time: 1.59 s
2
</pre>
TicketncohenWed, 07 Dec 2011 10:15:13 GMT
https://trac.sagemath.org/ticket/11735#comment:10
https://trac.sagemath.org/ticket/11735#comment:10
<blockquote class="citation">
<p>
I hope someone will later be able to improve the running time of the algorithm. Current implementation is quite slow for an O(m) algorithm compared to other (nicely impleted) algorithms with higher complexity
</p>
</blockquote>
<p>
Yep <code>:-/</code>
</p>
<p>
Thanks for the review, though ! <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerFri, 09 Dec 2011 10:21:08 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11735#comment:11
https://trac.sagemath.org/ticket/11735#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.8.alpha4</em>
</li>
</ul>
Ticket