Multi-list Ranking (MLR)

Input

A set $L = \{l_1, \ldots, l_q\}$ of lists, where each list $l_j$, $1 \leq j \leq q$, contains one or more integers; an integer $e$, which is an element of some list; and a designated integer $i$.

Problem

Does element $e$ receive a rank less than or equal to $i$?

Definitions

The rank of each element is computed iteratively as follows: assign a rank of one to all of the first elements of all lists; delete all occurrences of first elements from all lists; repeat this procedure on the updated lists after incrementing the value of the rank. The procedure is iterated as long as one list is nonempty.

Status

$\P$-complete (Dessmark, Lingas, and Maheshwari [1]).

Remarks

The reduction to show hardness is from GMSP.

If there are only $O((\log n)^k)$ lists, the problem can be solved in $\mathsf{SC}^{k+1}$. The authors show that in this case the problem is hard for the class $\mathsf{SC}^k$. For a variant of the problem with $k$ lists, each of size at most $n$, they provide an $O(\log n)$ time, $n^{k+1}$ processor CREW-PRAM algorithm.

Several other restrictions of the problem are considered and polylogarithmic time PRAM algorithms are given for them. See [1] for further details. The original motivation for looking at this problem was to investigate the complexity of SCH.