Hi,
The Graph.is_chordal function can be used to return a chordless cycle
on non-chordal graphs, but the implementation seems to be wrong.
Example (ran on the sagenb.org server):
sage: g = Graph({3:[2,1,4],2:[1],4:[1],5:[2,1,4]})
sage: g.is_chordal()
=> False
sage: _, g1 = g.is_chordal(certificate=True); g1.is_chordal()
=> True
Currently, the function proceeds as follows:
1. run algorithm LexBFS to find a vertex ordering which would be a
perfect-elimination-order (PEO) if G is chordal.
2. check if this ordering satisfies the PEO-property w.r.t. G, and if
not, remember the last vertex (i) in the PEO which violates it.
(assume G is not chordal)
3. let G' be the vertex induced subgraph of G corresponding to all
vertices occuring after (i) in the PEO.
4. find two non-adj. vertices (j), (k) in G', which were both adj. to
(i) in G.
5. find a shortest path between them in G', and return the vertex
induced subgraph consisting of this path plus (i).
The resulting cycle is not necessarily chordless, since the shortest
path can contain another neighbour (x) of (i), resulting in the chord
{x,i}.
One linear-time solution is given in [1]. I think it is not hard to
modify the code to use this.
[1] Addendum: Simple Linear-Time Algorithms to Test Chordality of
Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic
Hypergraphs.
http://dx.doi.org/10.1137/0214020
Regards,
Jan
--
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-support
URL: http://www.sagemath.org
