Function simulation, graph grammars and colourings

Abstract

We prove that to any partial function ϕ defined on a finite set, there corresponds an infinite class of graphs that could be generated by a graph grammar such that each graph in the class represents the function in the sense that evaluation of the function at any point x of its domain can be simulated by finding the unique extension of a partial vertex colouring of the graph specified by x. We show that in the proposed setup, generating such simulator graphs as well as finding the colouring extensions can be computed effectively in polynomial time. We also discuss some applications of this scenario in producing instances of the graph colouring problem near its phase transition that can be applied in a cryptographic setting.

Keywords:

• graph grammars/amalgams
• function evaluation
• reversible computation
• sequential graph colouring
• uniquely colourable graphs
• defining sets

2010 AMS Subject Classifications:

• 05C15
• 05C85
• 68Q42
• 68R01
• 03D15

Acknowledgements

The authors thank Arash Ahadi for drawing their attention to 35. They also thank him and the anonymous referees for their constructive comments.

Notes

Actually, this can be generalized for any given algorithm and can be used in cryptographic application. However, we do not delve into the details of this approach.

Although this is essentially all we need to prove our main results, the above setup can be extended to more complicated combinations such as recursion in classical recursion theory and theory of computation. We do not discuss the general setup in this article (see e.g. 7). Also, all the results of this article can be generalized to the case of effective simulation of relations with appropriate changes made in the definitions and algorithms. We do not delve into the details of such a generalization either since it will not give rise to stronger results as far as the main motivations of this article are concerned.

In this article, we use the term hyperedge for a graph that behaves as an edge with respect to its terminal ends (e.g. see Proposition 3.1), and the term edge replacement is used for the replacement of a simple edge by such a structure. This wording is chosen to be in coherence with well-known concepts in the theory of graph transformations (e.g. see 11).

Actually, it suffices to use a path to prove this result but we may emphasize that the construction can be used in a variety of ways (see Section 5).

Note that here the simple edge replacement rule only is applied to the edges e [x, y] that appear in the coding ⟨ H [x; y; R] ⟩ _Q .

This construction has redundancies since in this article we are more concerned about simplicities than optimizations. Of course, in real applications one can use more optimized encodings that will lead to smaller and more efficient trapdoors.