Splittable stack

Question

What is known about data structures that can maintain a sequence of items subject to the following two operations?

• Push(x): add x to the end of the sequence, and return an identifier for its position in the sequence
• Extract(S): given an unordered set of identifiers, remove the items in those positions from the sequence, and return a list of the removed items in sequence order

If you like you can think of this as a stack or a queue with a split operation that splits it into two stacks: the extract operation can be used to implement a pop or dequeue operation, and the extracted sequence of items could as well be put back again into a different stack or queue.

What I already know: one can maintain the sequence as a doubly-linked list, where each identifier is just a pointer to a linked-list node, and each node also stores a position number that allows fast comparisons between the positions of two unrelated elements in the sequence. It's not difficult to update the position numbers as the data structure progresses so that they are all positive integers of maximum value $O(n)$, where $n$ is the current number of items in the list. With this data structure, the only difficult part of an extract operation is sorting the extracted items by their position numbers. An extraction of $k$ items takes $O(k\sqrt{\log\log k})$ expected randomized time using the integer sorting algorithm of Han and Thorup from FOCS 2002, for instance, and a push operation takes constant time.

What I don't know: is it possible to handle extract in $O(k)$ time and push in constant time? Is there literature on this problem? Is it as hard as integer sorting?

Motivation: this is the basic step needed to order the items in the Coffman-Graham scheduling algorithm, which also has applications in graph drawing. The hard part of Coffman-Graham is a lexicographic topological ordering. This can be done by maintaining, for each different indegree, a sequence of the vertices with that indegree in the subgraph induced by the remaining vertices. Then, repeatedly remove the first vertex $v$ from the sequence of zero-indegree vertices and add it to the topological order; extract the neighbors of $v$ from the degrees they previously belonged to and push them onto the sequence for the next smaller degree. So an $O(k)$ time for the extract operations in this data structure would lead to a linear time implementation of the Coffman-Graham algorithm.

Since originally asking this I found a paper by Sethi from 1976 that allows the Coffman–Graham algorithm to be implemented in linear time, and included it in my Wikipedia article on the Coffman–Graham algorithm, so the original motivation is less meaningful. I'm still curious what the answer is, though.

Answer 1

I think this is at least as hard as sorting a set of integers $S \subseteq [n]$ with "random advice" of size polynomial in $n$. By random advice I mean that for any $n$ there is a fixed distribution ${\cal D}_n$ (depending only on $n$) over strings of size poly($n$) and our algorithm (modeled by a RAM machine) is given random access to a single sample from ${\cal D}_n$. ${\cal D}_n$ is the (randomized) data structure after pushing $[n]$ in order, together with a hash table that maps integers to identifiers in expected $O(1)$ time.

Given that setup, for an instance $S \subseteq [n]$ of the integer sorting problem, we can issue extract($S$) (actually we need the identifiers of $S$ but this mapping can be done in $O(1)$ time per item using the hash table that is part of the advice) and the input will be sorted in the time it takes to execute extract.

So, the message is that, unless some "free" side information that depends only on the upper bound of the integers can make integer sorting easier, extract is as hard as integer sorting.

Does this imply a relation between the two problems without the weird model? Is this notion of random advice something known? This is sort of like a MA protocol, but Merlin's message is not allowed to depend on the input and we care about Arthur's running time.