Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?
- $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
- $link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph $G$
- $unlink(G,a,b)$: Removes the edge from $a$ to $b$ in $G$
- $add(G,a)$: Adds a vertex to G
- $remove(G,a)$: Removes a vertex from G
A few notes:
- If we disallowed $unlink$, it seems it would be easy to maintain the connectedness information, using a disjoint-set type data structure.
- Obviously, $isConnected$ could be implemented using depth or breadth-first search, using the naive pointer-based representation of the graph. But this is inefficient.
I'm hoping for amortized constant or logarithmic time for all three operations. Is this possible?