Is this combinatorial optimization problem NP-hard?

Question

I working on a combinatorial optimization problem that I suspect is NP-hard, and a genetic algorithm has been working well with our dataset. We're a research group and plan to publish our results in our field (not in math or CS), and I'd like to explore the NP-hard question before sending the manuscript out for review.

There are two main questions:

1) I'd like to know whether this particular optimization problem has been studied. I've heavily searched the lit but haven't seen anything exactly the same.

2) If the problem hasn't been studied, I might take a crack at doing a reducibility proof, and would like some pointers to good NP-complete candidates for the reduction.

The problem can be described in two ways, as a subsequence variant, and as a bipartite graph problem.

In the subsequence flavor, I want to find a "relaxed" subsequence that allows permutations, and optimize to minimize the permutation count. For example: (. = any other char)

Query: abc, Target: ..b.a.b.c., Result: abc (normal subsequence)

Query: abc, Target: ..b.a.c.a., Result: bac (subsequence with one permutation)

The bipartite formulation is a matching problem or linear assignment problem, with the graph partitioned into query character nodes and target character nodes. The edges connect the query characters to the target characters, such that there is exactly one edge from each query char to a target char. The objective function is to minimize the number of edge crossings (also called "crossing number" in the lit). This is similar to bipartite graph layout algorithms that reorder node placement to minimize edge crossings, but my problem requires the that both node orders stay fixed.

Any thoughts from the experts on questions 1 or 2?

Thanks in advance!

Answer 1

Just some idea: Does it somehow equivalent to finding the minimal number of swap needed to sort an array (MIN-SBR)? If yes, this is NP-Hard.

(btw, are you working on something similar to this?)

Answer 2

I don't think this is NP-hard. See work by Pevzner and Hannehali. A paper that comes to mind is titled ``From Cabbage to Turnip''. The idea is to find the minimum number of inversions to go from one string to another. They have a polytime algorithm for this.