An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties:

• Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-structures)

• The accessible DAG is kept as a transitive reduction (notwithstanding other helper data-structures)

• It should be optimized for a sparse graph (adjacency lists)

• It should condense cycles as they are introduced, keeps a mapping between equivalent vertices that are all replaced with one "representative" vertex

• Ability to quickly answer quickly ancestor/descendant/transitive/relationship queries (in $\mathcal{O}(1)$ or $\sim\mathcal{O}\left(\log \left|V\right|\right)$ time)

• Should support vertex, edge insertion, deletion would be nice too

• Mutable operations (such as insertion) should be as output-sensitive as possible; in other words, the complexity should depend as much as possible on how much the operation must change the graph

• Ability to record changes over an operation, if requested. Obviously this might necessarily increase the complexity, but the increase should be output-sensitive. Examples:

• set of deleted vertices (due to condensation)

• set of deleted edges (due to reduction)

• set of new decendent relationships from $u$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(u,t)\in G'\wedge path(u,t)\not\in G\right\}$ )

• set of new ancestor relationships from $v$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(t,v)\in G'\wedge path(t,v)\not\in G\right\}$ )

The closest I can find is here, implementation. I think you can build on this to do have most of the properties I list, but I am wondering if there is anything better/well known, or perhaps if there is a name for this problem.

EDIT:
Related:

• What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

• What is the fastest deterministic algorithm for incremental DAG reachability?

• Does an algorithm exist to efficientl

Some keywords to help you search for related work: dynamic transitive closure, dynamic reachability problem, dynamic cycle detection. Because you want to allow both insertions and deletions, this is known as fully dynamic transitive closure.

Alternatively, you might want to consider whether there could be some structure in the particular graphs that arise in your setting that might help you build schemes that are faster than the general case.

StackExchange Computer Science Q#14798, answer score: 5