Skip to main content

Questions tagged [vertex-cover]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
0 answers
64 views

W[t]-containment of partial covering problems

I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
xtyner's user avatar
  • 81
3 votes
2 answers
817 views

Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
Saeed's user avatar
  • 3,440