Opened 7 years ago

Closed 7 years ago

#11735 closed defect (fixed)

Bug in is_chordal

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-4.8
Component: graph theory Keywords:
Cc: lsampaio, ddestrada, dcoudert Merged in: sage-4.8.alpha4
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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 :

Apply:

[1] https://groups.google.com/d/topic/sage-support/rU1VTz1Ou_I/discussion

Attachments (1)

trac_11735.patch (2.8 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 7 years ago by ncohen

  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by ncohen

  • Cc ddestrada added
  • Description modified (diff)

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

Changed 7 years ago by ncohen

comment:3 Changed 7 years ago by ncohen

  • Cc dcoudert added

(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 #11961. I thought of updating the discussion, but forgot about the ticket itself ^^;)

Nathann

comment:4 Changed 7 years ago by dsm

Are we lucky enough that these patches fix #10899 en passant?

comment:5 Changed 7 years ago by ncohen

No it should not :-)

Nathann

comment:6 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert

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.

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

So, what's wrong ?

David.

comment:7 Changed 7 years ago by dcoudert

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...

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

Nathann, am I right this time ? D.

comment:8 Changed 7 years ago by ncohen

Well, this graph clearly contains a long hole (induced cycle). Sage can find it too, with the "certificate" flag :

sage: G.is_chordal(certificate = True)
(False, Subgraph of (): Graph on 50 vertices)
sage: G.is_chordal(certificate = True)[1].show()

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).

Nathann

comment:9 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

You're right Nathann. I should not try a patch after a long day of work...

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).

So I'm positive with this patch.

Thank you Nathann.

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

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

comment:10 in reply to: ↑ 9 Changed 7 years ago by ncohen

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

Yep :-/

Thanks for the review, though ! ;-)

Nathann

comment:11 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.8.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.