10984 - Double NP-hard

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sat Feb 04, 2006 8:09 am

I got ..P.E (the 50-th PE) at last
Thanks Hadi and kp for your explanations
Thanks Adbenego, nice problems :)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10984 - Double NP-hard

Post by DD » Sun Mar 13, 2011 10:39 pm

It is really a nice problem. Since minimum vertex cover and maximum independent set are dual, with clever combinations and modifications this problem become polynominal time solvable. Thanks problem setter :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: 10984 - Double NP-hard

Post by Abednego » Sun Mar 13, 2011 11:46 pm

You are welcome. I'm glad you liked it.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 109 (10900-10999)”