time-complexitynetworkxcomplexity-theorydirected-acyclic-graphsisomorphism

What is the complexity of networkx.is_isomorphic?

What is the complexity of networkx.is_isomorphic(graph1, graph2)? I am particularly interested to know it in the case of directed acyclic graphs.

Cheers.

Solution

  • According to the documents of nx.is_isomorphic the vf2-algorithm is implemented and even the original scientific reference is given.

    "L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “An Improved Algorithm for Matching Large Graphs”, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001."

    The boost library states for the vf2-algorithm the following complexity:

    "The spatial complexity of VF2 is of order O(V), where V is the (maximum) number of vertices of the two graphs. Time complexity is O(V^2) in the best case and O(V!·V) in the worst case."