Solved

Clique np problem

Posted on 2007-11-27
7
280 Views
Last Modified: 2008-02-01
Hi Fellow EE Experts

Looking for a quick proof here on the following. one showing it can be done and an example showing it cant.

Looking at the following NP Problem.
http://en.wikipedia.org/wiki/Clique_problem

How would I show that for one instance an example can be solved in a finite amount of time and the other an exponential?

Any Help would be grealty appreciated.

Many Thanks
Steve
0
Comment
Question by:Stephen Manderson
  • 5
  • 2
7 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 20362535
You can show it is in  NP-Complete  by reducing it to Independent Set
http://en.wikipedia.org/wiki/Independent_set_problem
0
 
LVL 84

Expert Comment

by:ozo
ID: 20362564
Any given instance of the problem can be solved in P time by an algorithm that knows the answer to that given instance.
But for any given algorithm there exist instances of the problem that cannot be solved in polynomial time, unless every other NP-Complete problem can also be solved in Polynomial time,
0
 
LVL 84

Expert Comment

by:ozo
ID: 20362609
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 84

Expert Comment

by:ozo
ID: 20362613
0
 
LVL 19

Author Comment

by:Stephen Manderson
ID: 20362746
Thanks for the links Ozo tryiong to understand the way to prove for one instance the graph could be P time.

You say reducing it to an independent set, but isnt an independant set the opposite of a clique ?

Hmm im pretty lost when it comes to this, just to help me along the right lines would this be correct in trying to prove a clique problem in p time?

6
  \
   4-----5----
   I       I     1
   3-----2----

The clique is formed from vertices 1,2 and 5 which could be solved in p time

However

If there was an exponential amount of vertices it would be NP to calculate if a clique is present?
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 20363585
The time to solve is generally a function of the number of vertices.
If there was an algorithm that could solve any instance of the problem in a time that was a polynomial function of the number of vertices, then there would be an algorithm to solve any NP-C problem in polynomial time.
Since no one knows how to do that, no one knows how to write a deterministic algorithm that can solve any instance of clique in polynomial time.
This does not prevent there from being an algorithm that can quickly solve a particular instance of clique.

But it doesn't really make sense to say that a particular problem can be solved in exponential time,
Exponential time and polynomial time describes how the time to solve varies as function of the size of the problem.
0
 
LVL 19

Author Comment

by:Stephen Manderson
ID: 20364069
Sorry i meant that as the number of vertices increases so does the time taken to solve the problem.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

If you want to move up through the ranks in your technology career, talent and hard work are the bare necessities. But they aren’t enough to make you stand out. Expanding your skills, actively promoting your accomplishments and using promotion st…
If you get continual lockouts after changing your Active Directory password, there are several possible reasons.  Two of the most common are using other devices to access your email and stored passwords in the credential manager of windows.
The Bounty Board allows you to request an article or video on any technical topic, or fulfill a bounty request to earn points. Watch this video to learn how to use the Bounty Board to get the content you want, earn points, and browse submitted bount…
Articles on a wide range of technology and professional topics are available on Experts Exchange. These resources are written by members, for members, and can be written about any topic you feel passionate about. Learn how to best write an article t…

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now