Algorithmic Construction of Tessellation Cover to QUBO Formulations

The tessellation cover number on graphs is an NP-hard optimization problem important to model staggered walks in quantum computation. A tessellation is a partition of the vertices of a graph into vertex disjoint cliques. The tessellation cover problem aims to determine the minimum number t of tessellations that covers all edges of a given graph G. We denote by t-tessellability the decision version where it is asked if G admits a tessellation cover number of size t. Tessellations on graphs also have an interesting value for graph theory, since the tessellation cover number parameter T(G) is related to several others in the literature such as chromatic number, chromatic index, and maximum clique. In this study, we develop QUBO formulations for the following NP-hard problems: the determination of the maximum induced star on G, which yields a lower bound on T(G); the determination of the chromatic number of the clique graph of G and the chromatic index of G, which yield upper bounds on T(G); the determination of T(G), by transforming t-tessellability to integer programming and then to QUBO. In order to demonstrate the order-based formulation presented, we implement and analyze these formulations.