Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#7600 closed enhancement (fixed)

Vertex cover

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: kevin.stueve Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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

Attachments (1)

trac_7600.patch (4.1 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 9 years ago by kevin.stueve

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

comment:4 Changed 9 years ago by kevin.stueve

  • Cc kevin.stueve added

comment:5 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:6 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

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

comment:7 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

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

Changed 9 years ago by ncohen

comment:8 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

fixed !

comment:9 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:10 Changed 9 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 Changed 9 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.