Is this dynamic graph problem solvable?

Hi, I need a help. I came up with following subproblem while working on another problem. Can you confirm if its a recognized problem. I have spent months but couldn’t make any progress.

Design a data structure that maintains a directed graph. A node with node_id=0 is created by default, having no edges. The data-structure supports following queries:

  1. Create() : Create a new node with node_id assigned from an auto-incrementing counter. Add a directed edge from node-0 to this new node; return node_id of new node.

  2. Add(x, y) : Add a directed edge from node-x to node-y. Ignore if there is already an edge from x to y.

  3. Delete(x, y) : Delete the directed edge from node-x to node-y and also delete all the nodes (and their edges) of graph which are not reachable from node-0. return the list of deleted edges and nodes.

All queries should work in amortized complexity O(log(N)), where N is the number of nodes in the graph at the time of query.


what do you mean with querie? What querie the queries? If I understand it right the delete operation can’t be O(log(N)), there can be a delete operation where N-1 nodes need to be deleted