Splittable stack

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.

• If insertions happen only at the end of the sequence, you can mantain both a double linked list and an hash table of the items positions. Insertion: amortized O(1) (just keep a pointer to the last item). Extraction of k items: amortized O(k) (for each element of S, get pointer and remove it from hash table, get and remove item from list and add it to the extraction result). – Marzio De Biasi Apr 7 '11 at 6:58
• It's not extraction of the items from the list that takes the time, it's rearranging them from the unsorted order of the argument to Extract into the correct sequence order. – David Eppstein Apr 7 '11 at 7:10

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.

• Pushing $[n]$ onto $\mathcal{D}_n$ requires $\Omega(n)$ time, so having free access to $\mathcal{D}_n$ is like having $\Omega(n)$ computation already done at the start of the algorithm. As you can sort $k$ integers drawn from $[n]$ in $O(n+k)$ time, there's no reason to expect that sorting with free access to this data structure would take more than $O(k)$ time. – Dave May 8 '11 at 19:55
• You do have $\Omega(n)$ computation given for free, however access is not free: each query is charged as a time step. Can you design ${\cal D}_n$ so that you can sort $k$ integers with $O(k)$ queries to a string drawn from ${\cal D}_n$? – Sasho Nikolov May 8 '11 at 20:23
• Here's the reason I don't find this answer entirely convincing. If you only have one set S of integers that you want to sort, everything is linear time (just do counting sort in O(n+k)). But if you're trying to use this data structure to simulate a sequence of many small sorts (so that counting sort isn't good enough) then only the first of these small sorts is completely unconstrained: after that, you've removed some of the elements of [n], so each sequence you sort has to be disjoint from the previous ones. So it seems difficult to make a reduction from sorting work. – David Eppstein May 9 '11 at 5:17
• @David Eppstein: for $\ell$ sorts you can take $\ell$ copies of the initial data structure. Of course, the weird "random advice" model is not entirely convincing, we'd like a reduction in the usual sense. But the message I was conveying is that an $O(k)$ query time implies that an integer sorting algorithm can benefit from advice independent from its input in a memory-access efficient way. This is counterintuitive to me, but my intuition is weak here. BTW, I thought $O(n+k)$ is not the kind of linear time you are happy with? – Sasho Nikolov May 9 '11 at 5:39
• If you're copying the data structure once for each use, you're using $\Omega(n)$ time to make a copy for each sort, so this doesn't result in faster sorting. If you just query positions in a string representing $\mathcal{D}_n$ as you seem to be suggesting, it's unclear that this is sufficient to sort in $O(k)$ time. The data structure could change during an extract operation, and running on a static version could increase the runtime. – Dave May 9 '11 at 8:07