Search

The concept of graph tessellation cover was defined in the context of quantum walk models, and is a current research area in graph theory. In this work, we propose a generalization called total tessellation cover. A tessellation of a graph G is a partition of its vertex set V ( G ) into vertex disjoint cliques. A tessellation cover of G is a set of tessellations that covers its edge set E ( G ) . A total tessellation cover of G consists of a tessellation cover together with a compatible vertex coloring, such that the color of each vertex is different from the tessellation labels of the edges incident to the vertex. The total tessellation cover number T t ( G ) is the size of a minimum total tessellation cover of G . We present lower bounds T t ( G ) ≥ ω ( G ) and T t ( G ) ≥ s ( G ) + 1 , where ω ( G ) is the size of a maximum clique, and s ( G ) is the number of edges of a maximum induced star subgraph. A graph G is called a good total tessellable if T t ( G ) = ω ( G ) or T t ( G ) = s ( G ) + 1 . We study the complexity of the k - total tessellability problem, which aims to decide whether a given graph G has T t ( G ) ≤ k . We prove that k - total tessellability is in P for good total tessellable graphs. We establish the NP -completeness of the k - total tessellability when restricted to the following graph classes: bipartite graphs, line graphs of triangle-free graphs, universal graphs, ( 2 , 1 ) -chordal graphs and planar graphs.

The t -admissibility problem aims to decide whether a graph G has a spanning tree T in which the distance between any two adjacent vertices of G is at most t . In this case, G is called t -admissible, and the smallest t for which G is t -admissible is the stretch index of G . A complementary prism of G , denoted by G G ¯ , is obtained by the union of G with its complement G ¯ and the addition of a perfect matching between corresponding vertices of G and G ¯ . One of the challenges of the t -admissibility problem is to determine 3-admissible graph classes, since the computational complexity of such a problem remains open for more than 25 years. Moreover, it is known that recognizing 4-admissible graphs is, in general, an NP -complete problem (Cai and Corneil, 1995), as well as recognizing t -admissible graphs for graphs with diameter at most t + 1 , for t ≥ 4 (Papoutsakis, 2013). We prove that any graph G , non-complete graph, can be transformed into a 4-admissible one, by obtaining G G ¯ . Furthermore, we prove that the stretch indexes of G G ¯ graphs are equal to 4, and since they have diameter at most t + 1 , we present a class for which t -admissibility is solved in polynomial time. G G graphs are the Cartesian product G × K 2 , defined by the union of two copies of G and the addition of a perfect matching between corresponding vertices of the two graphs G . Interestingly, we prove that for G G graphs, whose definition is very similar to G G ¯ ’s, t -admissibility is NP -complete. Generalizing these constructions, we prove that determining t -admissibility is NP -complete for graphs that have perfect matching.

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.

The t-admissibility problem aims to decide whether a graph G has a spanning tree T in which the distance between any two adjacent vertices of G is at most t. Regarding its optimization version, the smallest t for which G is t-admissible is the stretch index of G, denoted by σ T ( G ) . The problem of deciding whether σ T ( G ) ≤ t , t ≥ 4 is NP -complete and polynomial-time solvable for t = 2 . However, deciding if t = 3 is an open problem. We determine 3-admissible graph classes by studying graphs with few P 4 's, and we partially classify the P vs NP -complete dichotomy of the t-admissibility problem for ( k , l ) -graphs. These graph classes generalize some others in which the computational complexity of the t-admissibility problem was already determined. Moreover, we determine the stretch index for cycle-power graphs and for ( 2 , 1 ) -chordal graphs, which are subclasses of ( k , l ) -graphs and the t-admissibility problem is NP -complete.

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. One important problem is the Closest Genome Problem (CGP), that aims to find, for a given distance notion, a genome that minimizes the maximum distance to any other, which can be seen as finding a genome in the center of all others. The Hamming Closest String Problem (Hamming-CSP) was already studied and settled to be NP-complete. In this paper, we show that the CGP is NP-complete for well-known genome rearrangement distances, such as the single-cut-or-join, the breakpoint and the block interchange.

Genome rearrangement problems aim at finding the minimum number of mutational events required to transform a genome into another. Studying such problems from a combinatorial point of view has been proved to be useful for the reconstruction of phylogenetic trees. In this work we focus on the relations between genome rearrangement and graph convexity in the following way. Graph convexity problems deal with input sets of vertices and try to understand properties on the closure of such inputs. In turn, the concept of closure is useful for studies on genome rearrangement by suggesting mechanisms to reduce the genomic search space. Computational complexity studies are widely developed in graph convexity problems, since there are several types of convexities, each capturing a distinct way of defining what is meant by “closure”. In this regard, considering the Hamming distance of strings, we solve the following problems: decide whether a given set is convex; compute the interval and the convex hull of a given set; and determine the convexity number of a given graph. All such problems are solved for the geodesic and monophonic convexities. On the other hand, for the Cayley distance of permutations, we study convexity of sets and interval determination of sets, in the context of the geodesic convexity.

Genome rearrangements are events where large blocks of DNA exchange pieces during evolution. The analysis of such events is a tool for understanding evolutionary genomics, in whose context...

A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The t-tessellability problem aims to decide whether there is a tessellation cover of the graph with t tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove \(\mathcal {NP}\)-completeness for t-tessellability if the instance is restricted to planar graphs, chordal (2, 1)-graphs, (1, 2)-graphs, diamond-free graphs with diameter five, or for any fixed t at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm.

A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The $t$-tessellability problem aims to decide whether there is a tessellation cover of the graph with $t$ tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove $\mathcal{NP}$-completeness for $t$-tessellability if the instance is restricted to planar graphs, chordal (2,1)-graphs, (1,2)-graphs, diamond-free graphs with diameter five, or for any fixed $t$ at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm., 13 pages, 5 figs, accepted in Latin 2018

Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation [Formula: see text] algorithm, whose running time was improved to O(nlogn) by Feng and Zhu (2007) with a data structure they defined, the permutation tree. Elias and Hartman (2006) developed a 1.375-approximation O(n(2)) algorithm, and Firoz et al. (2011) claimed an improvement to the running time, from O(n(2)) to O(nlogn), by using the permutation tree. We provide counter-examples to the correctness of Firoz et al.'s strategy, showing that it is not possible to reach a component by sufficient extensions using the method proposed by them. In addition, we propose a 1.375-approximation algorithm, modifying Elias and Hartman's approach with the use of permutation trees and achieving O(nlogn) time.

Sorting by transpositions is a challenging classic problem proposed in genome rearrangement and recently settled as NP-hard. Although the proven hard to sort $3$-permutations are close to the identity, the historical approach has been to study distant permutations, possible candidates to be diametral. The transposition diameter is a related challenging problem, known only for $n \leq 15$. We advance the study of both transposition distance and diameter by considering lonely permutations and the union operation. We present tighter bounds for the distance of lonely $3$-permutations, $u_{n,n-1}$, $u_{n,\frac{n}{2}}$, $u_{n,3}$, and $u_{n,4}$. We set the current lower bound for the transposition diameter back to $\big\lfloor\frac{n+1}{2}\big\rfloor+1$ and propose an alternative union of lonely permutations contributing to the approach used so far in the literature.

Sorting by Transpositions is an NP-hard problem for which several polynomial time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation algorithm, whose running time was improved to O(n logn) by Feng and Zhu (2007) with a data structure they defined, the permutation tree. Elias and Hartman (2006) developed a 1.375-approximation algorithm that runs in O(n 2) time. In this paper, we propose the first correct adaptation of this algorithm to run in O(n logn) time.

Determining the transposition distance of permutations was proven recently to be \(\textup{NP}\)-hard. However, the problem of the transposition diameter is still open. The known lower bounds for the diameter were given by Meidanis, Walter and Dias when the lengths of the permutations are even and by Elias and Hartman when the lengths are odd. A better lower bound for the transposition diameter was proposed using the new definition of super-bad permutations, that would be a particular family of the lonely permutations. We show that there are no super-bad permutations, by computing the exact transposition distance of the union of two copies of particular lonely permutations that we call knot permutations. Meidanis, Walter, Dias, Elias and Hartman, therefore, still hold the current best lower bound. Moreover, we consider the union of distinct lonely permutations and manage to define an alternative family of permutations that meets the current lower bound.