#12743: Addition of reduction rules as pre-processing of the vertex cover
function
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Old description:
> This patch does the following
>
> 1. Moves the vertex_cover function from generic_graph.py to graph.py.
> The function is valid only for graphs and the independent_set function
> was already in graph.py.
> 1. Simplifies the independent_set function so that it calls the
> vertex_cover function.
> 1. Adds basic reduction rules as a pre-processing of the vertex cover
> function. These reduction rules are the 4 basic rules described for
> instance in
> http://people.scs.carleton.ca/~dehne/projects/clustalxp/ACFLSS.pdf, that
> is:
> 1. Vertices of degree 0 are not part of the cover
> 1. The neighbor of a vertex of degree 1 is in the cover
> 1. If the neighbors of a degree 2 vertex are incident, they are in the
> cover
> 1. If the two neighbors v,w of a degree 2 vertex u are not incident,
> then either u is in the cover or v and w are in the cover.
>
> This is particularly useful for sparse graphs.
>
> More advanced reduction rules can also be considered (crown
> decompositions, etc.) but are not part of this patch.
>
> APPLY:
> * [attachment:trac_12743_reduction_rules_for_vertex_cover.patch]
> * [attachment:trac_12743-review.patch]
> * [attachment:trac_12743-review2.patch]
> * [attachment:trac_12743-doctest.patch]
New description:
This patch does the following
1. Moves the vertex_cover function from generic_graph.py to graph.py. The
function is valid only for graphs and the independent_set function was
already in graph.py.
1. Simplifies the independent_set function so that it calls the
vertex_cover function.
1. Adds basic reduction rules as a pre-processing of the vertex cover
function. These reduction rules are the 4 basic rules described for
instance in
http://people.scs.carleton.ca/~dehne/projects/clustalxp/ACFLSS.pdf, that
is:
1. Vertices of degree 0 are not part of the cover
1. The neighbor of a vertex of degree 1 is in the cover
1. If the neighbors of a degree 2 vertex are incident, they are in the
cover
1. If the two neighbors v,w of a degree 2 vertex u are not incident,
then either u is in the cover or v and w are in the cover.
This is particularly useful for sparse graphs.
More advanced reduction rules can also be considered (crown
decompositions, etc.) but are not part of this patch.
APPLY:
* [attachment:trac_12743-combined.patch]
--
Comment:
I did the following:
* Change the way the copy of the graph is performed to work with a copy
without labels (if any)
* Merge all patch into a single one to ease manipulations.
This patch is now working properly but needs an extra round of review.
I did some tests on large graphs (maps of the Internet by CAIDA) and the
MILP algorithm returns the vertex cover in less than a minute (the graph
has 36.000 nodes), but the Cliquer algorithm failed. On smaller instances
(20.000 nodes), the running time of Cliquer is significantly reduced when
using the reduction rules, but the improvement is unclear with the MILP.
For small graphs, Cliquer is generally faster than MILP.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:16>
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.
