Paper Info
Title
A Computational Complexity Comparative Study Of Graph Tessellation Problems
Abstract
A tessellation of a graph is a partition of its vertices into cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges, and the tessellation cover number, denoted by T(G), is the size of a smallest tessellation cover. The t-TESSELLABILITy problem aims to decide whether a graph G has T(G) <= t. The number of edges of a maximum induced star of G, denoted by s(G), is a lower bound on T(G). In this work we define good tessellable graphs as the graphs G with T(G) = s(G), and we introduce the corresponding gOOd TESSELLABLE RECOgNITION (gTR) problem, which aims to decide whether G is a good tessellable graph. We show that gTR is NP-complete not only if T(G) can be obtained in polynomial time or s(G) is fixed, but also when the gap between T(G) and s(G) is large. We establish graph classes that present distinct computational complexities considering problems related to the parameters T(G) and s(G), and we perform a comparative study of the gTR, t-TESSELLABILITy, and STAR SIzE problems, where the STAR SIzE problem aims to decide whether the number of edges a maximum induced star of a graph is at least a given number. (c) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2020.11.045
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Structural graph theory, Computational complexity, Tessellation cover, Equivalence covering
Journal
858
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
7
Name
Order
Citations
PageRank
Alexandre Abreu100.34
Luís Felipe I. Cunha235.85
Celina de Figueiredo300.34
Luis Kowada400.34
F. L. Marquezino5196.66
Renato Portugal65210.01
Daniel Posner700.34