title: Is this combinatorial optimization problem NP-hard?
body: <p>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.  </p>
  
  <p>There are two main questions:  </p>
  
  <p>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.  </p>
  
  <p>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.</p>
  
  <p>The problem can be described in two ways, as a subsequence variant, and as a bipartite graph problem.  </p>
  
  <p>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)</p>
  
  <p>Query: abc, Target: ..b.a.b.c., Result: abc   (normal subsequence)</p>
  
  <p>Query: abc, Target: ..b.a.c.a., Result: bac   (subsequence with one permutation)</p>
  
  <p>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.  </p>
  
  <p>Any thoughts from the experts on questions 1 or 2?</p>
  
  <p>Thanks in advance!</p>