0
$\begingroup$

Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other sequence. But there should not be any line crossing. And each line could be assigned with a weight(controlled by relation between two connected points) and the overall weights should be as low as possible.

Is this an NP problem? Can this problem be reduced to any of Karp's 21 NP-complete problems?

Thanks to David Richerby. The constraints that were missing are that the number of points that are not connected to any points should also be as few as possible.

$\endgroup$
  • $\begingroup$ Do you mean NP-hard instead of NP? You have two targets (maximize weights and minimize points that are not connected), how do you balance them? $\endgroup$ – xskxzr Oct 27 '18 at 19:20
0
$\begingroup$

You could prove that something is in NP by reducing it to an NP-complete problem. However, it's usually much easier to just demonstrate a nondeterministic polynomial-time algorithm that finds a solution, and even easier to demonstrate a deterministic polynomial-time algorithm that verifies a given solution.

Now, the trivial answer to your question is "No, this is not in NP" because there's a type error. NP is a class of decision problems (i.e., problems where the answer is "yes" or "no"), whereas your problem is to compute some object that minimizes some criterion. However, the decision version of your problem is in NP: this is the problem where you're given a target weight $w$ and asked if there's a solution with weight at most $w$. It's easy to check deterministically in polynomial time that a proposed solution does have weight at most $w$.

Beyond that, there's not much to say. Your problem seems under-specified to me because the trivial solution "Don't match anything at all" has weight zero, which is best possible as long as the weights are non-negative. If you tighten up the definition of the problem, my guess is that the non-crossing requirement constrains the problem so much that it will have a deterministic polynomial-time solution. For example, if you match the first element of sequence $A$ to anything other than the first element of sequence $B$, then the first element of sequence $B$ can't be matched to anything without crossing. This suggests that dynamic programming will give an efficient solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.