I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following:

Given two graphs g1(V, E) and g2(V, E), find a graph G(V, E) where V(g1) ⊆ V(G), V(g2) ⊆ V(G), E(g1) ⊆ E(G) and E(g2) ⊆ E(G). I use adjacency list to store data and merge two graphs by visiting vertex/edge. However, the time complexity is higher than O(n2). Is any better algorithm?

  • $\begingroup$ In the absence of any other conditions on $G$, you seem to be asking about how to find the union of two sets (once for the vertices, and once for the edges), which can be done in $O(\alpha(n))$ time, where $\alpha(x)$ is the inverse Ackermann function. $\endgroup$ – András Salamon Jul 13 '18 at 12:26

If a vertex is only in one subgraph then its adjacency list will not change. However if a vertex is in both subgraph, then you simply take union of its adjacency list in subgraphs g1 and g2. You don't need to traverse any edge more than twice in case of undirected graph and once in case of directed.

Therefore it takes O(|V| + |E|) time where |V|,|E| are total vertices and edges in graph G


Maybe my solution is just too trivial and therefore wrong, but here is my pseudo-algorithm:
Select any $v \in V_{G1}$
Select any $u \in V_{G2}$
Create a new Edge e with $e=(v,u)$
$G=(V,E)$ would be $(V(G1) \cup V(G2),E(G1) \cup E(G2) \cup e)$then. As far as I see this algorithm would fit into that what you want and you can guess the complexity (what actually should be n in your question?).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.