This page is an overview of open questions that might be relevant and still need more research to be answered properly:

  1. A lot of papers only provide an isomorphism test and no canonization algorithm. In theory we could use the core of a CPQ itself as the key for the index. When matching an input CPQ against the index we would them have to perform isomorphism tests against all index items. This is obviously slower than having to compare two canonical representation, which can be done in constant or linear time usually. However, on the other hand canonization algorithms are typically less efficient than isomorphism testing algorithms. Moreover, isomorphism testing has many conditions that allow the algorithm to short circuit with a “No” answer (e.g. different vertex count, different node degrees). Therefore it’s possible that testing for isomorphism against all index items is faster for few index entries (or when short circuiting conditions are commonly applicable). On the other hand there is likely a turning point when the extra computation required for canonization would be worth the trade off. The real question is if this turning point is before or after the index has grown to a realistic size. Likely this answer depends a lot on the involved graphs, but this would allow us to use algorithms that do not have a canonization version.

  2. In various papers there are mentions that it is possible to convert an edge labelled graph into an unlabelled graph. This would allow us to use canonization algorithms that cannot deal with edge labels at the cost of an increased runtime due to the graph transformation and increased graph size (assuming the edge unlabelled does not have a significantly faster runtime). Could such transforms be a viable approach to solve the problem? Do these transforms preserve the answer to the isomorphism question for the original graphs?

  3. Similarly, would a transform exist that transforms a directed graph into an undirected graph. A cursory search seems to suggest that such a transform does exist. But would it be viable to use here and does it preserve to answer to the isomophism test between the original input graphs.

  4. Regular treewidth is defined for undirected graphs. A quick search seems to suggest that an extension to directed graphs does exist (also by Seymour & Thomas). This might be relevant to further look into.

  5. From the thesis for nishe it would seem that a specific class of graphs (Miyazaki graphs) is problematic for popular existing tools to deal with (at least in 2009). If these graphs are still problematic it might be worth seeing how much these graphs overlap with CPQ query graphs as this could potentially be a performance issue.