#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 )
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)
Change History (12)
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
comment:4 Changed 11 years ago by
- Cc kevin.stueve added
comment:5 Changed 11 years ago by
- 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 11 years ago by
- 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 11 years ago by
- 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 11 years ago by
comment:9 Changed 11 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:10 Changed 11 years ago by
- Merged in set to sage-4.3.rc1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:11 Changed 11 years ago by
- Milestone changed from sage-4.3.1 to sage-4.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 problemIMO, would be better with the word "an" in place of "a".
Kevin Stueve