Vertex cover

[nathanncohen]

As the title says, this patch implements Graph.vertex_cover.

You could be in need of #7270 and GLPK from http://sagemath.org/packages/optional/glpk-4.38.p4.spkg depending on the version of Sage you are using !!!

CC: @sagetrac-kevin-stueve

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7600

[sagetrac-kevin-stueve]

comment:3

I've never reviewed a patch before.

We were just talking about vertex cover in my algorithms class the other day.

The three problems:

1. Does G have a clique of size m or more?

2. Is there a vertex cover of size m or less for G?

3. Does G contain an independent set of size m or more?

are all polynomially reducible to each other.

exercise 9, p 403, The Design and Analysis of Algorithms, 2nd Edition

I'm not aware if those other problems are implemented in Sage. If not, maybe a ticket should be created.

3048 As vertex cover is a NP-complete problem

IMO, would be better with the word "an" in place of "a".

Kevin Stueve

[nathanncohen]

comment:5

Hello !!!!

You are right, these three are reducible to each other ! Actually, Sage already has an algorithm for 1) and 3) through Cliquer, which is way more efficient that LinearProgramming... I will immediately add several lines to the patch to let it use Cliquer by default, and use LP if the users wants it ( and this way we can control the respective values of the two algorithms ) :-)

Thank you very much for your remark, this should speed up the algorithm amazingly ! :-)

Nathann

[nathanncohen]

comment:6

Done ! Thank you very much for your help ! :-)
Besides, as the algorithm Cliquer does not require GLPK or CBC, there is a way for everybody to compute a vertex cover now :-)

Nathann

[rlmill]

comment:7

oops:

sage: vc2 = g.vertex_cover(algorithm="Cliquer")
---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)

/Users/rlmill/.sage/temp/rlm_book.local/98560/_Users_rlmill__sage_init_sage_0.py in <module>()

/Users/rlmill/sage-4.3.rc0/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in vertex_cover(self, algorithm, value_only, log)
   3325                 return self.order()-len(independent)
   3326             else:
-> 3327                 return set(g.vertices()).difference(set(independent))
   3328 
   3329         elif algorithm=="MILP":

UnboundLocalError: local variable 'g' referenced before assignment

[nathanncohen]

Attachment: trac_7600.patch.gz

[nathanncohen]

comment:8

fixed !

[rlmill]

Reviewer: Robert Miller

[rlmill]

Author: Nathann Cohen

[mwhansen]

Merged: sage-4.3.rc1