A seemingly simple problem proven hard

Posted on 2014 03 21 by phimuemue

Consider the following problem: You are celebrating a festival and want to invite \(n\) guests. The only problem is the following: You want to distribute all guests in a single row, but you can only place to guests next to each other if they get along with each other. The question is if there's an efficient (meaning poly-time) algorithm computing such an order of guests. To put it in a nutshell: In general, there is probably (unless P=NP) no efficient procedure computing such a valid sequence of guests efficiently.

This can be quite naturally seen by reducing the NP-complete HAMILTON to the given problem: Given any graph \(G\), we interpret its vertices as guests. We say that two guests get alogn with each other if there is an edge connecting the corresponding vertices. This is a quite natural tranformation of HAMILTON to our problem.

The rest is easy: We can easily show that the given problem is in NP, because we can check the correctness of a solution in polynomial time. Thus, the problem itself is NP-complete.

Special cases might be solved efficiently

Even if this problem can (probably) not be solved efficiently generally, we note the following: If we impose some restrictions onto the original problem (guests at a festival), we might be able to compute a solution efficiently. E.g. we can express guests as numbers and say that two guests get alogn with each other if their numbers are both even resp. odd. Then, we just have to check whether there are as many even as odd numbers and put them alternating (even-odd-even-odd-...) one after another.

Another example could be that two numbers (guests) get along, if their sum is less than a given maximum value. In this case, we can employ a greedy algorithm to construct an optimal solution.

So the question arises, why - in those cases - the reduction from HAMILTON isn't working. It is simply the fact that not all graphs (i.e. not all HAMILTON problems) can be transformed into problem instances with the additionally imposed restrictions. For example, consider the even-odd case: A graph containing 3 vertices (guests) and no edges (i.e. no guest is compatible to any other guest) - this graph does not correspond to any valid problem instance with the restriction that two guests get along if their numbers are both even resp. odd.

In particular, when reducing problems, we have to ensure that each original problem has a corresponding case in the target problem description.