TY - GEN
T1 - Algorithmic Construction of Tessellation Cover to QUBO Formulations
AU - Cunha, Luís
AU - Marquezino, Franklin
AU - Posner, Daniel
AU - Romaneli, Matheus
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - graph theory
KW - quadratic unconstrained binary optimization
KW - quantum computing
KW - tessellation cover number
UR - https://link.springer.com/chapter/10.1007/978-981-97-7801-0_19
UR - https://www.scopus.com/pages/publications/85205519925
U2 - 10.1007/978-981-97-7801-0_19
DO - 10.1007/978-981-97-7801-0_19
M3 - Conference paper
SN - 9789819778003
VL - 15180 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 220
EP - 232
BT - Algorithmic Aspects in Information and Management - 18th International Conference, AAIM 2024, Proceedings
A2 - Ghosh, Smita
A2 - Zhang, Zhao
PB - Springer
CY - Singapore
ER -