3
$\begingroup$

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Alternatively, given an oracle for finding both the subsequence and length of the Longest Common Subsequence between two sequences, it's easy to find $\text{LIS}(A)$: Given a sequence $A$, sort $A$ into $A'$, and calculate $\text{LCS}(A,A')$.

This question is prompted by the fact that there are $O(n\log n)$ algorithms for LIS but not LCS. On a separate note, are there any results comparing the hardness of the two problems or giving a superlinear/quadratic lower bound to LCS?

$\endgroup$
  • $\begingroup$ Was my answer helpful? Have you considered accepting my answer? $\endgroup$ – Apass.Jack Aug 15 at 23:14
2
$\begingroup$

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Well, we can find $\text{LCS}(A,B)$ without any call to the oracle since we can just run any algorithm that finds $\text{LCS}(A,B)$ such as brutal force or a solution by dynamic programming.

What you intended to ask was how much we can reduce the time-complexity of algorithms that find $\text{LCS}(A,B)$ if the oracle is available. The time-complexity will consist of two parts. One part comes from ordinary operations, and the other part comes from the calls to the oracle. There are two questions here.

Question one. Can we use less ordinary operations (asymptotically) with the availability of the oracle?

Question two. If we can, how few calls to the oracle are needed to lower the complexity of the ordinary operations?

When one of $A$ and $B$ consists of distinct elements

Suppose the elements in $A$ are distinct. Here is an algorithm that employs the oracle. The idea of the algorithm is that if we regard the natural order of elements in $A$ according to the indices as defining a strictly increasing order, a common subsequence of $A$ and $B$ is exactly an increasing subsequence of $B$.

  1. Keeping $A$ intact, sort $A$ into a new sequence $\alpha$.
  2. Initialize a new sequence $I$.
  3. For $i$ from 0 to size($B$) exclusive, try finding the index $j$ such that $A[j]$ is $B[i]$. If found, append $\alpha[j]$ to $I$.
  4. Return the length that is returned by the oracle given sequence $I$.

There are two ways to implement step 2.

  • If the elements in $A$ and $B$ can be totally ordered, we can sorted the elements in $A$, keeping track of each element's index in $A$. Then a binary search can find that index $j$.
  • Construct a hash set whose elements are $(A[i],i)$ for all $i$, where the hash depends only on $A[i]$. Then we can use the hash set to find that index $j$.

So an answer to question one and two is that we can use a single call to the oracle to lower the complexity of the ordinary operations from $O(nm)$ to

  • $O(n\log n + m \log n)$ when $m\gg\log n$ or
  • $O(m)$ if the operation of finding an element in a hashset is considered $O(1)$.

Here $n$ is the number of distinct elements in one array and $m$ is the number of the elements in the other array.

When both $A$ and $B$ contain duplicate elements

It is not clear how we can take advantage of the oracle in order to reach a positive answer to question one. Instead, here is a conditional hardness result.

It is not possible to find $LCS(A,B)$ in time $O(n^{2 - \epsilon})$ for any positive constant $\epsilon$ where $n$ is the length of $A$ and $B$, if we can assume the strong exponential time hypothesis. This is shown in Tight Hardness Results for LCS and Other Sequence Similarity Measures by Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams, 2015.

$\endgroup$
  • $\begingroup$ If the oracle can returns the length for the Longest Increasing Subsequence of a given integer sequence, then the algorithm can be simplified by a) appending $j$ to $I$ in step 3 and b) removing step 1. $\endgroup$ – Apass.Jack May 13 at 19:03

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.