Main Topics

CPQ-Core-based index design

The first step is breaking up an arbitrary input query into CPQs (how is not relevant for this project).

Then given a CPQ compute it’s core, which is a graph homomorphic to the original graph and of smallest size. This means that the core can always be computed for a given CPQ. This then raises the question if the smallest homomorphic graph is unique? Maybe multiple smallest graphs exist. It was proven by Seiji that all cores for a CPQ are unique up to isomorphism, so this is not an issue.

Once we have the unique core of a CPQ. We then compute a canonical representation of this graph. The exact best way to do this is still unknown and the main topic of this project. One way would be to use an existing canonization algorithm that can deal with CPQs as input, an overview of existing methods is being created. Alternatively we could look for a method that is not generalized and instead only applicable to bounded treewidth graphs. This is favourable as CPQs have a treewidth of 2, so fixed parameter tractable (FTP) algorithms exponential in the treewidth would be ideal. Finally, a novel canonization technique tailor made for CPQs would be an option.

Regarding isomorphism testing

The complexity class of the graph isomorphism class is poorly known1. We do not know of any algorithms that solve the problem in polynomial time (for the general case), but at the same time we also did not prove that the problem is NP-complete. Recent work hints that it is instead quasi-polynomial2.

Graph canonization

The graph canonization problem is the problem of finding a canonical representative for a graph $G$ that is unique for the entire isomorphism class associated with $G$. In other words, the canonical representative is the same for all graphs isomorphic to $G$. Moreover, if and only if two graphs share the same canonical representation then the graphs are isomorphic.

References:

  1. Bloyet, N., Marteau, P.-F., Frenod, E.: Scott: A method for representing graphs as rooted trees for graphcanonization. In: International Conference on Complex Networks and Their Applications, pp. 578–590 (2019). Springer, Cham
  2. László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 684–697. ACM, 2016