School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 307,004
  • Replies: 841,477
  • Topics: 140,611
  • Snippets: 4,466
  • Tutorials: 1,166
  • Total Online: 1,966
  • Members: 108
  • Guests: 1,858

Welcome to Dream.In.Code
Become an Expert!

Join 307,004 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,966 people online right now. Registration is fast and FREE... Join Now!




Polynomial Clique Algorithm?

 

Polynomial Clique Algorithm?, I'm a undergrad in CS -- and I'm cautiously optimistic
ded8381

12 Feb, 2009 - 03:15 PM
Post #1

New D.I.C Head
*

Joined: 12 Feb, 2009
Posts: 1
Ok, so I'm in a CS course learning about P/NP -- and we came across the clique NP-Complete problem of finding a maximal clique. I thought of an algorithm that seemed to me would be polynomial. I went home and coded it, and it seems to me... it's polynomial time. I tested it by generating random graphs, and then also on fully connected graphs. On random graphs it runs at n^2.1, on a complete graph it runs at n^2.89

The way I determined that is by running it on graph of size 500,550,600,etc... to 2000. Then I took the log(count) and log(size), and then x = log(count)/log(size), giving me consistently the numbers I mentioned above.

If anyone has any advice of how I could test it, I would be appreciative. Thanks!
User is offlineProfile CardPM
+Quote Post


LaFayette

RE: Polynomial Clique Algorithm?

13 Feb, 2009 - 04:47 AM
Post #2

D.I.C Regular
Group Icon

Joined: 24 Nov, 2008
Posts: 258



Thanked: 29 times
Dream Kudos: 25
My Contributions
Start preparing yourself for a life of (academical) fame!
User is offlineProfile CardPM
+Quote Post

Gloin

RE: Polynomial Clique Algorithm?

18 Feb, 2009 - 02:51 AM
Post #3

Expert Schmexpert...
Group Icon

Joined: 4 Aug, 2008
Posts: 3,613



Thanked: 143 times
Dream Kudos: 75
My Contributions
Unfortunately or actually Fortunately it's very unlikely that you found a polynomial time algorithm for this problem.

If you wanna test your algorithm, give it a larger input, in the order of 1,000,000 nodes. This should still be solvable if the algorithm is better than n^3.
Try to find out what would cause the worst case for this algorithm. It might be that the cases you have tried are in general simple for this algorithm while some worst case could cause it to fail.

What type of algorithm technique is it using?

Don't be discouraged if you find out that the algorithm isn't finding the optimal solution in polynomial time, it may very well be that you've found a very good approximation or near optimal polynomial time algorithm.
User is online!Profile CardPM
+Quote Post

arushgadkar

RE: Polynomial Clique Algorithm?

16 Jul, 2009 - 08:47 AM
Post #4

New D.I.C Head
*

Joined: 16 Jul, 2009
Posts: 1
Hello,
the clique program that you have written..... is it for finding all maximal cliques in a graph or just one maximal clique. I need a code (C++) for finding all maximal cliques. Would it be possible for you to share the code you have written.

Thanks
Arush.
User is offlineProfile CardPM
+Quote Post

Neumann

RE: Polynomial Clique Algorithm?

16 Jul, 2009 - 11:27 AM
Post #5

I can judge a book by its cover
Group Icon

Joined: 8 Jul, 2009
Posts: 686



Thanked: 93 times
Dream Kudos: 225
My Contributions
The clique algorithm can indeed have a polynomial growth if the clique size equals to V - C where V is the total number of vertices and C is a constant. However, when you're dealing with with clique size of, for example 1/2 x V or 1/3 x V etc... the algorithm is NP-Complete.

Besides, you weren't properly calculating the growth of your algorithm. You were simply adding a constant amount to your input size. That doesn't eliminate the constant factors in the Big-O of your algorithm which make it hard to properly assess the rate of growth. Do this:

Record the number of operations your algorithm performs. Double the input and record the number again. Compare the ratios, that should tell you how fast the algorithm is growing with respect to the input.

This post has been edited by Neumann: 16 Jul, 2009 - 11:31 AM
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 06:50AM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month