Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Matemática Contemporânea

Bounds and Complexity for the Tessellation Problem

Alexandre Abreu, Luis Cunha, Tharso D. Fernandes, Celina M.H. de Figueiredo, Luis Antônio Brasil Kowada, Franklin de Lima Marquezino, Daniel Posner, Renato Portugal

Published Jan 1, 2017• 4 citations
Publisher
DOI
10.21711/231766362017/rmc453

Related papers

Algorithmic Construction of Tessellation Cover to QUBO Formulations

Luís Cunha, Franklin de Lima Marquezino, Daniel Posner +1 more

Lecture notes in computer science•Jan 1, 2024•0 citations

Tessellations on Graphs: Theory, Algorithms, and Complexity.

Alexandre Abreu

Due to recent technological advances, quantum computing has gained notoriety. In this paradigm, the concept of quantum walk is fundamental for the development of algorithms for quantum computers. Among the existing quantum walk models, the staggered model, proposed by Portugal et al. stands out, since it includes the Szegedy model as a particular case, and part of the coined model. The staggered model uses the concept of tessellations on graphs to generate the quantum evolution operators that perform the walker's movements on the graph. Tessellations on graphs also have an interesting value for graph theory, since the parameter \textit{tessellation cover number} $T(G)$ is related to several other parameters present in the literature such as \textit{chromatic number}, \textit{chromatic index}, \textit{total chromatic number}, \textit{independent set number}, and \textit{clique number}. In addition, problems related to $T(G)$, such as \textsc{$t$-tessellability}, \textsc{good tesellable recognition}, and \textsc{total good tessellable recognition} have deep relations with classic problems in graph theory involving graph coloring. In this work we present results in graph theory for the problems related to tessellations on graphs mentioned above, such as computational complexity, lower and upper bounds for $T(G)$, and the value of $T(G)$ for several graph classes. Furthermore, we present a quantum walk model based on \textit{total tessellation cover}, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.

•Jan 1, 2020•0 citations

Tight Bounds for Simon’s Algorithm

Xavier Bonnetain

Lecture notes in computer science•Jan 1, 2021•17 citations

Total tessellation cover and quantum walk

Alexandre Abreu, Luís Cunha, Celina M.H. de Figueiredo +3 more

We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on $T_t(G)$, which is the smallest number of tessellations required in a total tessellation cover of $G$. We highlight two of these lower bounds $T_t(G) \geq ω(G)$ and $T_t(G)\geq is(G)+1$, where $ω(G)$ is the size of a maximum clique and $is(G)$ is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either $T_t(G)=ω(G)$ or $T_t(G)=is(G)+1$. The $k$-total tessellability problem aims to decide whether a given graph $G$ has $T_t(G) \leq k$. We show that $k$-total tessellability is in $\mathcal{P}$ for good total tessellable graphs. We establish the $\mathcal{NP}$-completeness of the following problems when restricted to the following classes: ($is(G)+1$)-total tessellability for graphs with $ω(G) = 2$; $ω(G)$-total tessellability for graphs $G$ with $is(G)+1 = 3$; $k$-total tessellability for graphs $G$ with $\max\{ω(G), is(G)+1\}$ far from $k$; and $4$-total tessellability for graphs $G$ with $ω(G) = is(G)+1 = 4$. As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and $(2,1)$-chordal graphs.

arXiv:2002.08992•Feb 20, 2020•0 citations

Algorithmic Complexity

Fabio Benatti

Theoretical and mathematical physics•Jan 1, 2009•2 citations

The Relative Complexity of Approximate Counting Problems

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill +1 more

Algorithmica•Dec 10, 2003•196 citations
Due to recent technological advances, quantum computing has gained notoriety. In this paradigm, the concept of quantum walk is fundamental for the development of algorithms for quantum computers. Among the existing quantum walk models, the staggered model, proposed by Portugal et al. stands out, since it includes the Szegedy model as a particular case, and part of the coined model. The staggered model uses the concept of tessellations on graphs to generate the quantum evolution operators that perform the walker's movements on the graph. Tessellations on graphs also have an interesting value for graph theory, since the parameter \textit{tessellation cover number} T(G)T(G)T(G) is related to several other parameters present in the literature such as \textit{chromatic number}, \textit{chromatic index}, \textit{total chromatic number}, \textit{independent set number}, and \textit{clique number}. In addition, problems related to T(G)T(G)T(G), such as \textsc{ttt-tessellability}, \textsc{good tesellable recognition}, and \textsc{total good tessellable recognition} have deep relations with classic problems in graph theory involving graph coloring. In this work we present results in graph theory for the problems related to tessellations on graphs mentioned above, such as computational complexity, lower and upper bounds for T(G)T(G)T(G), and the value of T(G)T(G)T(G) for several graph classes. Furthermore, we present a quantum walk model based on \textit{total tessellation cover}, being pioneer in the use of vertices and edges as possible locations for the walker, simultaneously.
We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph, in contrast with previous models in which the walker hops either to vertices or edges. We establish bounds on Tt(G)T_t(G)Tt​(G), which is the smallest number of tessellations required in a total tessellation cover of GGG. We highlight two of these lower bounds Tt(G)≥ω(G)T_t(G) \geq ω(G)Tt​(G)≥ω(G) and Tt(G)≥is(G)+1T_t(G)\geq is(G)+1Tt​(G)≥is(G)+1, where ω(G)ω(G)ω(G) is the size of a maximum clique and is(G)is(G)is(G) is the number of edges of a maximum induced star subgraph. Using these bounds, we define the good total tessellable graphs with either Tt(G)=ω(G)T_t(G)=ω(G)Tt​(G)=ω(G) or Tt(G)=is(G)+1T_t(G)=is(G)+1Tt​(G)=is(G)+1. The kkk-total tessellability problem aims to decide whether a given graph GGG has Tt(G)≤kT_t(G) \leq kTt​(G)≤k. We show that kkk-total tessellability is in P\mathcal{P}P for good total tessellable graphs. We establish the NP\mathcal{NP}NP-completeness of the following problems when restricted to the following classes: (is(G)+1is(G)+1is(G)+1)-total tessellability for graphs with ω(G)=2ω(G) = 2ω(G)=2; ω(G)ω(G)ω(G)-total tessellability for graphs GGG with is(G)+1=3is(G)+1 = 3is(G)+1=3; kkk-total tessellability for graphs GGG with max⁡{ω(G),is(G)+1}\max\{ω(G), is(G)+1\}max{ω(G),is(G)+1} far from kkk; and 444-total tessellability for graphs GGG with ω(G)=is(G)+1=4ω(G) = is(G)+1 = 4ω(G)=is(G)+1=4. As a consequence, we establish hardness results for bipartite graphs, line graphs of triangle-free graphs, universal graphs, planar graphs, and (2,1)(2,1)(2,1)-chordal graphs.