# How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. )

The professor, asked me a way to evaluate the performance of my algorithm (not the program), but my algorithm is simply a brute force of all the possible cases, and I don't think you can do any better without heuristics, therefore I think the questions makes no sense (at least to me).

Am I wrong?

• Ask yourself the questions: How many possible cases are there? and How long does it take to try each case? – Tom van der Zanden Jan 18 '15 at 15:59
• OK, so you believe you can't do better. But how does that stop you evaluating the performance of the algorithm you actually have? It's like saying "My professor wants me to evaluate how long it will take to fly to Australia. But Australia is a really long way away and I don't think it's possible to get there faster than flying. So the question doesn't make sense." Of course it makes sense. – David Richerby Jan 18 '15 at 18:06
• Nono, maybe I was not clear enough. It's easy to state the asymptotic of the algorithm: (if I recall correctly) it should be O(Bell'sNumber(nodes)*edges*). Once we know this, the question remains: "is my algorithm good or bad?!" that's what puzzle me. – asdf Jan 19 '15 at 17:44

There are plenty of ways to go about dealing with NP-hard problems.

Even if you know the asymptotic upper bounds on worst-case runtime (more you usually don't get), you don't have information about

• the typical case and
• the precision of your bound.

In the absence of exact analyses, all you can do is run the algorithm on a representative sample of inputs and compare it to others.

To be clear, even though your algorithm has bad $O$-runtime (in the worst case) it does not always take this long to finish. Go find out!

Conducting meaningful runtime experiments is not trivial, and often done horribly wrong in the literature. I can recommend (the affordable) A Guide to Experimental Algorithmics by C.C. McGeoch (2012) for an introduction.

• That said, it's unlikely that brute force is better than at first glance. Try something smarter and you may be rewarded with better performance on chip if not on paper. (This happens; the most popular example is probably Simplex.) – Raphael Feb 18 '15 at 8:24

It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.

• We already know the asymptotic for my algorithm. That's why I don't get the meaning of the question. – asdf Jan 19 '15 at 17:44
• @asdf "The problem is NP-complete" tells you that there's a nondeterministic algorithm that runs in polynomial time. But your algorithm is deterministic so the problem being in NP tells you nothing about the running time of your algorithm. – David Richerby Feb 18 '15 at 8:19
• @DavidRicherby A problem being in some complexity class does not tell you anything about any algorithm for it, ever. – Raphael Feb 18 '15 at 15:57

Maybe your professor is asking you to implement and run your algorithm and evaluate the time it takes in different sizes of instances. As is brute force, maybe you can't go away to more than 20 vertices, but is still a good excercise.