Convexity properties of graphs
This class gathers the algorithms related to convexity in a graph. It implements the following methods:
ConvexityProperties.hull() | Returns the convex hull of a set of vertices |
ConvexityProperties.hull_number() | Computes the hull number of a graph and a corresponding generating set. |
These methods can be used through the ConvexityProperties object returned by Graph.convexity_properties().
AUTHORS:
- Nathann Cohen
Bases: object
This class gathers the algorithms related to convexity in a graph.
Definitions
A set of vertices is said to be convex if for all
the set
contains all the vertices located on a shortest path between
and
. Alternatively, a set
is said to be convex if the distances
satisfy
.
The convex hull of a set
of vertices is defined as the smallest
convex set containing
.
It is a closure operator, as trivially and
.
What this class contains
As operations on convex sets generally involve the computation of distances between vertices, this class’ purpose is to cache that information so that computing the convex hulls of several different sets of vertices does not imply recomputing several times the distances between the vertices.
In order to compute the convex hull of a set it is possible to write the
following algorithm.
For any pair `u,v` of elements in the set `S`, and for any vertex `w` outside of it, add `w` to `S` if `d_{G}(u,w) + d_{G}(w,v) = d_{G}(u,v)`. When no vertex can be added anymore, the set `S` is convex
The distances are not actually that relevant. The same algorithm can be
implemented by remembering for each pair of vertices the list of
elements
satisfying the condition, and this is precisely what this class
remembers, encoded as bitsets to make storage and union operations more
efficient.
Note
Possible improvements
When computing a convex set, all the pairs of elements belonging to the set
are enumerated several times.
Nothing says these recommandations will actually lead to any actual improvements. There are just some ideas remembered while writing this code. Trying to optimize may well lead to lost in efficiency on many instances.
EXAMPLE:
sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull([1,3])
[1, 2, 3]
sage: CP.hull_number()
3
TESTS:
sage: ConvexityProperties(digraphs.Circuit(5))
Traceback (most recent call last):
...
ValueError: This is currenly implemented for Graphs only.Only minor updates are needed if you want to makeit support DiGraphs too.
Returns the convex hull of a set of vertices.
INPUT:
EXAMPLE:
sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull([1,3])
[1, 2, 3]
Computes the hull number and a corresponding generating set.
The hull number of a graph
is the cardinality of a smallest
set of vertices
such that
.
INPUT:
COMPLEXITY:
This problem is NP-Hard [CHZ02], but seems to be of the “nice”
kind. Update this comment if you fall on hard instances
ALGORITHM:
This is solved by linear programming.
As the function associating to each set
its convex hull is a
closure operator, it is clear that any set
of vertices such that
must satisfy
for any proper
convex set
. The following formulation is hence
correct
Of course, the number of convex sets – and so the number of constraints
– can be huge, and hard to enumerate, so at first an incomplete
formulation is solved (it is missing some constraints). If the answer
returned by the LP solver is a set generating the whole graph, then
it is optimal and so is returned. Otherwise, the constraint
corresponding to the set
can be added to the LP, which makes the
answer
infeasible, and another solution computed.
This being said, simply adding the constraint corresponding to is
a bit slow, as these sets can be large (and the corresponding constrait
a bit weak). To improve it a bit, before being added, the set
is
“greedily enriched” to a set
with vertices for as long as
. This way, we obtain a set
with
, and the constraint corresponding to
–
which is stronger than the one corresponding to
– is added.
This can actually be seen as a hitting set problem on the complement of convex sets.
EXAMPLE:
The Hull number of Petersen’s graph:
sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull_number()
3
sage: generating_set = CP.hull_number(value_only = False)
sage: CP.hull(generating_set)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
REFERENCE:
[CHZ02] | F. Harary, E. Loukakis, C. Tsouros The geodetic number of a graph Mathematical and computer modelling vol. 17 n11 pp.89–95, 1993 |