Genome Rearrangements on Multigenomic Models: Applications of Graph Convexity Problems

Abstract

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 many rearrangement distances have been proposed, based on finding the minimum number of rearrangements to transform one genome into another, using some predefined operation. However, when more than two genomes are considered, we have new challenging problems. Studying such problems from a combinatorial point of view has been shown to be a useful tool to approach such problems, for example, the reconstruction of phylogenetic trees. We focus on genome rearrangement problems related to graph convexity. Such an approach is in connection with some other well-known studies on multigenomic models, for example, those based on the median and on the closest string. We propose an association between graph convexities and genome rearrangements in such a way that graph convexity problems deal with input sets of vertices and try to answer questions concerning the closure of such inputs. The concept of closure is useful for studies on genome rearrangement by suggesting mechanisms to reduce the genomic search space. Regarding the computational complexity, and considering the Hamming distance on strings, we solve the following problems: decide if a given set is convex; compute the interval and the convex hull of a given set; and determine the convexity number, interval number, and hull number of a Hamming graph. All such problems are solved for three types of convexities: geodetic, monophonic, and P₃. Considering the Cayley distance on permutations, we solve the convexity number and interval determination problems for the geodetic convexity.

1. Introduction

Phylogeny is the study of evolutionary relationships, and in an evolutionary scenario a fundamental question is to recognize similarities between species so that we can properly accomplish phylogeny reconstruction and understand in what extent mutational events affect pieces of DNA. Along the time axis, a sequence of mutations yields new sequences that are responsible to generate new species, and the reconstruction of phylogenetic trees is of central importance to systematize the morphological, chemical, and genetic data collections arising from such process. Several genome rearrangement-based methods for reconstructing phylogenetic trees are known (Fertin et al., 2009). In general, we are given a set of genomes and a table of distances between pairs of genomes computed beforehand, according to some metric (Sankoff and Blanchette, 1998), and then apply possible reconstruction strategies based on distance, on parsimony, on maximum likelihood, or on Bayesian inference (Li et al., 2004).

1.1. Multigenomic models

Sets of genomes are considered in some approaches. The median string (or permutation) problem with respect to a given metric aims at finding a solution string (or permutation) that minimizes the sum of its distances to all strings of the input set (Fertin et al., 2009). The closest string (or permutation) problem with respect to a given metric aims at finding a solution string (or permutation) s that minimizes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\max \{ dist ( s , x ) \} $$ \end{document} for x in the input set (Lanctot et al., 2003; Cunha et al., 2019). The correlation network analysis (Langfelder et al., 2013) tries to select, among several genes known by empirical evidence, the ones that play central biological roles. By genomic search space we mean the closure with respect to a genomic subset evolution (Irizarry et al., 2005).

Regarding metrics on strings, the Hamming and Cayley distances (Fertin et al., 2009) are the most known and easy to compute. Other metrics over permutations lead to intractable computations of distances, for example, the transposition distance (Bulteau et al., 2012).

Multigenomic models can lead to intractable problems even when the distances are easy to compute. The closest string/permutation problems with respect to the Hamming distance (Lanctot et al., 2003) and the Cayley distance are both NP-hard (Popov, 2007). The median problem with respect to the Cayley distance on permutations (Lanctot et al., 2003) is also NP-hard (but still open when the input set contains three permutations). In contrast, the median problem with respect to the Hamming distance on strings (Lanctot et al., 2003) is solvable in polynomial time.

1.2. Convexity problems

A genome can be modeled as a string over an alphabet or as a permutation, which is a restricted string where each letter appears exactly once, and a mutational event is represented by an operation that yields a distinct string or permutation. Moreover, a graph can represent these objects and the relationships between them. Vertices are strings (or permutations), and there exists an edge linking two vertices if and only if the distance between them is equal to one (Eriksson et al., 2001; Konstantinova, 2008).

Graph convexity is a rich field in which several combinatorial problems and convexity types can be defined according to the application at hand (Penso et al., 2015). In general, we deal with sets of vertices to be increased step by step by following some prescribed rule, until the process stabilizes into a convex set (the “closure” or convex hull).

By considering the closure of subsets, we propose in this study an association between graph convexity and genome rearrangement problems. A finite convexity space is a pair (V, C) consisting of a finite set V and a family \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal C}$$ \end{document} of subsets of V such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\emptyset \in {\mathcal C} , \,V \in {\mathcal C}$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal C}$$ \end{document} is closed under intersections. Members of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal C}$$ \end{document} are called convex sets. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} be a collection of paths of a graph G, and let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${I_P}:{2^{V ( G ) }} \to {2^{V ( G ) }}$$ \end{document} be a function (called interval function) such that

Distinct choices of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} lead to interval functions of quite different behavior. Such functions, in turn, are naturally associated with special convexity spaces (the so-called path convexities). For instance, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} contains precisely all the shortest paths in a graph then the corresponding interval function is naturally associated with the well-known geodetic convexity; if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} is the collection of induced paths then the corresponding interval function is associated with the monophonic convexity; and there are many other examples in the literature.

Since there is an exponential number of strings/permutations of length n, the corresponding graph G over such objects has order exponential in n. Even if a subset S of vertices of G has size polynomial in n, its closure may have size exponential in n. Thus, new challenges arise when trying to solve some typical graph convexity problems in the biological context proposed in this study.

1.3. Contributions

In this study, we propose various graph convexity problems on sets of strings/permutations, determining their solution in polynomial time, using the strategy of not explicitly listing the elements in the sets. Considering the Hamming distance on binary strings, we solve the following problems: decide if a given set is convex; compute the interval and the convex hull of a given set; and determine the convexity number, interval number, and hull number of a Hamming graph. All such problems are solved for three types of convexities: geodetic, monophonic, and P₃. Considering the Cayley distance on permutations, we solve the convexity number and the interval determination problems for the geodetic convexity. Finally, we relate graph convexity problems to the well-known closest string/permutation and median problems for some already studied metrics.

2. Background

2.1. Genome rearrangements

An alphabet Σ is a nonempty set of letters, and a string over Σ is a finite sequence of letters of Σ. A permutation π of length n is a bijection from the set {1,2,…,n} onto itself. We denote π = [π(1)π(2)⋯π(n)]. Note that it is a particular string, because π contains exactly one occurrence of each letter.

Genome rearrangements are events where large blocks of DNA exchange pieces during evolution. The analysis of these events is an important tool for understanding evolutionary genomics, a classical line of research in bioinformatics (Bafna and Pevzner, 1998; Fertin et al., 2009; Bulteau et al., 2012; Cunha et al., 2013, 2015, 2019). Genomes are represented either as strings of an alphabet or permutations of positive integers under some well-defined hypothesis. Such discrete model aims at finding the minimum number of operations to transform a given string into another one, or to transform a given permutation into the identity permutation, where the allowed operations are fixed beforehand.

2.1.1. Distance

The Hamming distance between two binary strings s and r of the same length, denoted by d_H(s, r), is defined as the number of mismatched positions between s and r. The Cayley distance between two permutations π and σ of the same length, denoted by d_C(π, σ), is the minimum number of element exchanges that transform one permutation into the other. More specifically, the Cayley distance of a permutation π of length n is the Cayley distance of π to the identity permutation ι = [1 2 3 … n].

A permutation can be represented by its permutation cycles with each element followed by its image. For instance, a cycle representation of [5 2 7 4 1 6 3] is (1 5)(3 7)(2)(4)(6). A k-cycle of a permutation is a cycle with k elements. Note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi ( \ell ) = \ell$$ \end{document} if and only if the cycle representation of π contains the 1-cycle \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \ell )$$ \end{document} , where the identity permutation of length n has n 1-cycles. Moreover, regarding the Cayley distance, if the permutation is not the identity permutation, then we can place an element in its correct position by creating a 1-cycle. Hence, given a permutation π with pc(π) permutation cycles, d_C(π) = n − pc(π).

Cayley graphs are useful to relationships between genomes (Konstantinova, 2008). Strings (or permutations) are associated with vertices, and two strings (or permutations) at distance one are neighbors. Note that there are 2ⁿ binary strings and n! permutations. Since these graphs have exponential number of vertices, then we have a new challenge because we must be able to solve convexity problems without constructing such graphs.

2.1.2. Median

In the Median Genome Problem (MGP) the goal is to find a solution genome that minimizes the sum of the distances between the solution and the genomes in the input. One of the applications of the MGP is related to reconstructing ancestral genomes. Many possible metrics are employed in this context. The breakpoint and the double-cut-and-join (DCJ) median problems are NP-hard (Pe'er and Shamir, 1998; Friedberg et al., 2008), but the single-cut-or-join (SCJ) median problem is solvable in polynomial time. Haghighi and Sankoff (2012) proved that, for the breakpoint metric, a tendency for the median is to fall onto or to be close to one of the input genomes, and this provides poor information for phylogeny reconstruction. They also conjecture that the same behavior applies to the DCJ metric.

2.1.3. Closest genome

Since in some cases medians give no new information, an alternative strategy is to solve the Closest Genome Problem (CGP), that aims to find a genome s that minimizes the maximum distance between s and a genome in the input set; this can be viewed as finding a genome in the “center” of all genomes in the input, that is, a genome corresponding to the radius of the input set. Lanctot et al. (2003) studied the CGP for the Hamming distance on strings and proved its NP-hardness. Popov (2007) studied the CGP for the Cayley metric on permutations, and showed that the Cayley–CGP is also NP-hard. Cunha et al. (2019) showed that the CGP is NP-hard for the breakpoint, SCJ, and block-interchange metrics. To the best of our knowledge, the CGP has not been studied in the context of other easily computable metrics.

2.2. Convexity problems in graphs

Let I be an operator to be applied to a subset S of vertices of a graph G. The set I(S) is obtained from S after a single application of I, in such way that an element z belongs to I(S) if and only if either z∈S or z satisfies a criteria associated with the convexity type. Some of these criteria are listed next. Recall Equation (1). In the geodetic convexity, the collection \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} is the collection of all the shortest paths of G. In the monophonic, P₃, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P_3^*$$ \end{document} convexities, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\mathcal P}$$ \end{document} is the collection of, respectively, all the induced paths of G, all the paths of length 2 of G, and all the induced paths of length 2 of G.

Besides various types of convexity, there are many well-established combinatorial problems in the field of graph convexity. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} , where V (G) denotes the vertex set of G. S is a convex set if I(S) = S. The interval number in(G) is the minimum size of a set S such that I(S) = V (G). The hull set H(S) of S is the set such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$H ( S ) = {I^{k + 1}} ( S ) = {I^k} ( S )$$ \end{document} for some integer k, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${I^0} ( S ) = S$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${I^{j + 1}} ( S ) = I ( {I^j} ( S ) )$$ \end{document} . The convexity number c(G) is the maximum size of a convex set of G distinct from V (G). The hull number hn(G) is the minimum size of a set S such that H(S) = V (G).

Hence, those problems are formalized as follows (we describe them in terms of their decision versions):

convex set—cs

input: A graph G and a set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} .

question: Is S convex?

interval determination—id

input: A graph G, a set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} , and a vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$z \in V ( G )$$ \end{document} .

question: Does z belong to I(S)?

convex hull determination—chd

question: Does z belong to H(S)?

convexity number—cn

input: A graph G and a positive integer r.

question: Is cn(G) ≥ r?

interval number—in

input: A graph G and a positive integer r.

question: Is in(G) ≤ r?

hull number—hn

input: A graph G and a positive integer r.

question: Is hn(G) ≤ r?

3. Convexities and the Hamming Distance

A graph representing the Hamming distances between binary strings of length n is the well-known n-dimensional cube graph Q_n. The vertex set of Q_n represents the strings belonging to {0,1}ⁿ, and two vertices are adjacent if and only if they differ in exactly one bit. In this section, G stands for the n-dimensional cube Q_n.

3.1. convex set

3.1.1. Geodetic

Let G[S] be the subgraph induced by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} . If G[S] is isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{n \prime }}$$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n \prime = { \log _2} \vert S \vert < n$$ \end{document} , then between any two vertices of S the vertices of all shortest paths linking them are in S, since a vertex v outside \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{n \prime }}$$ \end{document} is associated with a string s_v such that s_v[j] (the bit at position j in s_v) satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${s_v} [ j ] \ne {s_u} [ j ]$$ \end{document} for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \in S$$ \end{document} , that is, there is no shortest path between two vertices of S through v. (Note that, since G[S] is an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n \prime$$ \end{document} -dimensional cube, there is at least one position j such that s_u[j] has the same bit value for all u ∈ S.) Conversely, suppose that G[S] is not isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{n \prime }}$$ \end{document} for any value of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n \prime$$ \end{document} . Let k be the minimum integer for which S is entirely contained in a subgraph H of G isomorphic to the k-dimensional cube Q_k. In this case, there exists at least one vertex v of H such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$v \notin S$$ \end{document} and there is a shortest path between two vertices of S through v. Hence S is not convex, since v ∈ I(S).

Theorem 1 Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} . In the geodetic convexity, S is convex if and only if G[S] is isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{n \prime }}$$ \end{document} where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n \prime = { \log _2} \vert S \vert$$ \end{document} .

We can decide in polynomial time if S is isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{n \prime }}$$ \end{document} , since we must have (a) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert = {2^{n \prime }}$$ \end{document} ; (b) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n - \vert S \vert$$ \end{document} positions have with the same bit value in all strings s_u for u ∈ S.

3.1.2. Monophonic

It is clear that S is convex for the cases |S| = 1, |S| = 2 (with two adjacent elements), and S = V (G). Conversely, suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$2 < \vert S \vert < \vert V ( G ) \vert$$ \end{document} . Then there exist three vertices u, v, w in S such that u is not adjacent to v, because G is bipartite and contains no triangles. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert < \vert V ( G ) \vert$$ \end{document} , there is an induced path between u and v through a vertex x ≠ w, because G is biconnected. This implies that S is not convex.

Theorem 2 Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} . In the monophonic convexity, S is convex if and only if |S| = 1, or |S| = 2 with two adjacent elements, or S = V (G).

Theorem 3 Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} . In the P₃ and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P_3^*$$ \end{document} convexities, we can check if S is convex in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

3.2. interval determination

3.2.1. Geodetic

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$z \in V ( G )$$ \end{document} . Then z belongs to I(S) if and only if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d ( {s_i} , z ) + d ( z , {s_j} ) = d ( {s_i} , {s_j} )$$ \end{document} , for some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${s_i} , {s_j} \in S$$ \end{document} . We can easily determine such distances by a pairwise check of agreeing positions (those with identical bit values). Hence the following:

Theorem 4 geodetic-id is solvable in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

Note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$I ( S ) = {Q_{n \prime }}$$ \end{document} for some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n \prime \le n$$ \end{document} , that is, I(S) is convex. Thus, I(S) = H(S).

3.2.2. Monophonic

If S contains two nonadjacent vertices u and w, we show by induction on n that any every vertex v in G = Q_n lies in an induced path between u and w.

Note that Q_n can be obtained by adding a perfect matching between two copies A and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} of Q_n−₁ in such a way that every vertex x in A is linked to its copy \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \prime$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} . Suppose first that u and w are in A and v in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} ; in this case we can construct an induced path going from u to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} , then from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w \prime$$ \end{document} passing through v (using induction), and finally from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w \prime$$ \end{document} to w. If u, w, and v are in A then, by induction, there is an induced path from u to w through v entirely contained in A. If u is in A and w in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} then there is, by induction, an induced path from the vertex in the same copy of v, say u, to v; from v the path continues to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$v \prime$$ \end{document} and, finally, to w. Hence the following:

Theorem 5 In the monophonic convexity, if S contains two nonadjacent vertices then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$I ( S ) = H ( S ) = \;V ( G )$$ \end{document} .

Note that if S is a clique then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert = 2$$ \end{document} , because the clique number of Q_n is two. In this case, by Theorem 2, S is convex. Hence the following:

Theorem 6 Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq V ( G )$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$z \in V ( G )$$ \end{document} . In the monophonic convexity, z is in I(S) if and only if either S contains two nonadjacent elements or S = {z,x} for a vertex x adjacent to z.

Theorem 7 P₃-id and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P_3^*$$ \end{document} -id are solvable in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

3.3. convex hull determination

As seen in Section 3.2, in the geodetic and monophonic convexities we have that I(S) = H(S) for any S.

Theorem 8 geodetic–chd and monophonic–chd are solvable in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

Theorem 9 P₃-CHD and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P_3^*$$ \end{document} -CHD are solvable in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

3.4. convexity number

3.4.1. Geodetic

In the geodetic convexity, if S is isomorphic to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{{{ \log }_2} \vert S \vert }}$$ \end{document} then S is convex, by Theorem 1. Suppose S is convex and has size >2ⁿ⁻¹. Then there is at least one vertex outside a hypercube of size 2ⁿ⁻¹, which implies that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert = {2^n} = \vert V ( G ) \vert$$ \end{document} . Hence the following:

Theorem 10 In the geodetic convexity, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c ( G ) = {2^{n - 1}}$$ \end{document} .

3.4.2. Monophonic

By Theorem 2, a set S strictly contained in V (G) is monophonically convex if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert = 1$$ \end{document} or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert = 2$$ \end{document} with two adjacent elements. Now, suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert \ge 3$$ \end{document} . Then, S contains a pair of nonadjacent vertices, and, by Theorem 5, the only convex set in this case is V (G). Hence the following:

Theorem 11 In the monophonic convexity, c(G) = 2.

Theorem 12 In the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}^*$$ \end{document} convexities, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c ( G ) = {2^{n - 1}}$$ \end{document} .

3.5. interval number

3.5.1. Geodetic

Consider a pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s , s \prime$$ \end{document} of complementary strings, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${s_j} = 1 - {s \prime _j}$$ \end{document} for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$j \in \{ 1 , \ldots , n \} $$ \end{document} . Then s and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s \prime$$ \end{document} are endpoints of a diametral path in G, and any z lies in a shortest path between s and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$s \prime$$ \end{document} , that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S = \{ s , s \prime \} $$ \end{document} is an interval set. Hence the following:

Theorem 13 In the geodetic convexity, in(G) = 2.

3.5.2. Monophonic

Recall from Theorem 5 that, in the monophonic convexity, if S contains two nonadjacent vertices then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$I ( S ) = H ( S ) = \;V ( G )$$ \end{document} . Hence the following:

Theorem 14 In the monophonic convexity, in(G) = 2.

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}^*$$ \end{document} convexities. In such convexities, S is an interval set of G if and only if every vertex outside S has at least two neighbors in S. Suppose G is formed by two copies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A , A \prime$$ \end{document} of Q_n₋₁ joined by a matching as previously described. Also, suppose that A is formed by two copies A₁, A₂ of Q_n₂, and, similarly, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} by copies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${A \prime _1} , {A \prime _2}$$ \end{document} , where every vertex of A_i is matched with a vertex of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${A_i}^ \prime ,\, i = 1 , 2$$ \end{document} . It is not difficult to see that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S = V ( {A_1} ) \cup V ( {A \prime _2} )$$ \end{document} is a minimum interval set of G where every vertex outside S has exactly two neighbors in S. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert V ( {A_1} ) \vert = \vert V ( {A \prime _2} ) \vert = {2^{n - 2}}$$ \end{document} , we have the following:

Theorem 15 In the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}^*$$ \end{document} convexities, in(G) = 2ⁿ⁻¹.

3.6. hull number

Recall from Section 3.5 that, in both the geodetic and monophonic convexities, we have in(G) = 2. In addition, in such cases, an interval set is also a hull set. Hence the following:

Theorem 16 In the geodetic and monophonic convexities, hn(G) = 2.

We first prove that there is a hull set S of G such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert \le n$$ \end{document} . If n = 2, this is trivially true. If n > 2, suppose that G is formed by two copies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A , A \prime$$ \end{document} of Q_n_-1 such that every x in A is matched with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \prime$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} . By induction, there is a hull set S_A of A such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert {S_A} \vert \le n - 1$$ \end{document} . Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S = {S_A} \cup \{ u \prime \} $$ \end{document} , for a vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} arbitrarily chosen. Note that every vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w \prime$$ \end{document} adjacent to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} is adjacent to two vertices in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$H ( {S_A} ) \cup \{ u \} $$ \end{document} , namely \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} and w. Thus, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$N [ u \prime ] \subseteq H ( S )$$ \end{document} . Now every vertex in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} at distance two from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \prime$$ \end{document} is adjacent to at least two vertices in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$H ( {S_A} ) \cup N [ u ]$$ \end{document} . Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} is a connected graph, this process continues until all vertices of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \prime$$ \end{document} are included in the convex hull of S. Hence S is a hull set of G and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert \le n$$ \end{document} .

Now we prove that any hull set S of G satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert \ge n$$ \end{document} . Note that, for any S, H(S) consists of a union of disjoint hypercubes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Q_{{n_1}}} , {Q_{{n_2}}} , \ldots , {Q_{{n_k}}}$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\max \{ {n_i} \} \le \vert S \vert$$ \end{document} (a single-vertex subgraph is considered in this study as a hypercube Q₀). Thus, S is a hull set if and only if k = 1 and n₁ = n. If contains fewer than n strings then S cannot be a hull set. Hence the following:

Theorem 17 In the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \textbf{\textit{P}}}_{ \textbf{\textit{3}}}^*$$ \end{document} convexities, hn(G) = n.

4. Geodetic Convexity and the Cayley Distance

4.1. convex set

From an algorithmic point of view, a set of permutations S in a Cayley graph is geodetically convex if and only if for any pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} of permutations in S, no permutation σ outside S lies in a shortest path between π and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} , that is, no σ outside S satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_C} ( \pi , \sigma ) + {d_C} ( \sigma , \pi \prime ) = {d_C} ( \pi , \pi \prime )$$ \end{document} , where d_C(a, b) stands for the Cayley distance between a and b. Note that this is clearly equivalent to the property “all the shortest paths between π and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} lie entirely in S.”

The distance d_C(a, b) can be easily computed in time polynomial in n (the length of the permutations). However, there might be a number of permutations outside S that is exponential in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} . Hence, the solution proposed in the previous paragraph does not guarantee a polynomial-time algorithm.

Another approach to check the convexity of S consists of, for each pair of distinct permutations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} in S, performing a breadth-first search in the Cayley graph, starting at π. This search produces the sets \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${S_1} , {S_2} , \ldots$$ \end{document} , such that S_j contains all the strings that are at distance j from π. Suppose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_C} ( \pi , \pi \prime ) = k$$ \end{document} . Each time a new permutation ρ∈S_j is reached during the search, the test “ \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_C} ( \rho , \pi \prime ) = k - j$$ \end{document} ” must be done. If the test is false, ρ is discarded and the search continues to a new permutation ρ. Otherwise, we have three cases: (a) if ρ∈S and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \ne \pi \prime$$ \end{document} then the search continues to a new permutation ρ; (b) if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \notin S$$ \end{document} then the search stops: ρ lies in a shortest path between π and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} but does not belong to S; (c) if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho = \pi \prime$$ \end{document} then the search stops: all the permutations lying in a shortest path between π and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi \prime$$ \end{document} have been visited. If the search stops at case (b) for some pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} then S is not convex; otherwise, all the searches succeed (for all pairs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} ), and S is convex. Each search clearly visits at most \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} permutations, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( \vert S{ \vert ^2} )$$ \end{document} searches are performed. Hence the following:

Theorem 18 cayley–cs can be solved in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

4.2. interval determination

As in Section 3.2, given a set of permutations S and a permutation σ, deciding if σ belongs to I(S) amounts to verifying if there is a pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} of permutations in S such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${d_C} ( \pi , \sigma ) + {d_C} ( \sigma , \pi \prime ) = {d_C} ( \pi , \pi \prime )$$ \end{document} . The Cayley distance between two permutations can be easily determined in linear time. Hence, by considering all possible pairs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\pi , \pi \prime$$ \end{document} in S × S, we have the following:

Theorem 19 cayley–id can be solved in time polynomial in n and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert S \vert$$ \end{document} .

5. Concluding Remarks and Relations between Convexity, Median, and Closest Solution Problems

The goal of this article is to propose a new tool to deal with genome sets, modeled as sets of strings or permutations (a widely used approach in genome rearrangement studies). There are interesting questions with respect to closest string/permutation or median problems, some of them hard in terms of computational complexity (Haghighi and Sankoff, 2012; Cunha et al., 2019). Other perspectives on genome sets include genomic subset closure and correlation genomic network analysis (Irizarry et al., 2005; Langfelder et al., 2013).

In this study we propose an association between closures of genome sets modeled as strings/permutations and genome rearrangements. This approach leads exactly to convexity problems in Hamming or Cayley graphs. Although the median and the closest string/permutation problems are NP-hard or still open for the Hamming or Cayley distances, we show that many convexity problems are solvable in polynomial time for such metrics.

Zanetti et al. (2013) proposed a rearrangement scheme based on matrices where the rank is the considered metric. In this scenario, they showed that a matrix in the intersection of three shortest paths is a solution for the median problem. Note that this solution is an element of the geodetic hull of the three input matrices. Hence, a new challenge is concerned with finding other metrics that preserve the property of having the median solution in the geodetic hull of the input set. The same occurs considering the SCJ distance over genomes (Feijao and Meidanis, 2011), since in such metric it is known that a median solution belongs to the adjacency of at least two of the input genomes.

Regarding the relationship between the geodetic convexity and closest string/permutation problems, an interesting question is whether a closest genome is in the convex hull of the input set S. By the triangular inequality, a necessary condition for a string to be the center with radius at most d is that the distance between any pair in the input string set must be at most 2d. Hence, if there is an input pair whose distance between the elements is 2d and there is a closest solution, then such solution is indeed in the geodetic hull, because it lies in a shortest path; in particular, such a closest solution belongs to I(S). If for all input pairs the distances are <2d and there is a closest solution with distance at most d for each input string, then we have that a solution belongs to the hull set H(S), since if such a closest solution does not lie in a shortest path between a pair of input strings, it will be in a shortest path at some iteration k (when I^k(S) is determined) for some pair.

Footnotes

Acknowledgments

This study is partially supported by the following Brazilian research agencies: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)—Finance Code 001, by the Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ), and by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq).

Author Disclosure Statement

The authors declare that no competing financial interests exist.

References

Bafna

, and Pevzner

P.A.

1998. Sorting by transpositions. SIAM J. Discrete Math. 11, 224–240.

Bulteau

, Fertin

, and Rusu

2012. Sorting by transpositions is difficult. SIAM J. Discrete Math. 26, 1148–1180.

Cunha

L.F.I.

, Feijão

, Santos

, et al. 2019. On the computational complexity of closest genome problems. Discrete Appl. Math. (in press). https://doi.org/10.1016/j.dam.2019.04.002

Cunha

L.F.I.

, Kowada

L.A.B.

, de

. Hausen

, et al. 2013. Advancing the transposition distance and diameter through lonely permutations. SIAM J. Discrete Math. 27, 1682–1709.

Cunha

L.F.I.

, Kowada

L.A.B.

, Hausen

R.D.A.

, et al. 2015. A faster 1.375-approximation algorithm for sorting by transpositions. J. Comput. Biol. 22, 1044–1056.

Cunha

L.F.I.

, and Protti

2018. Closure of genomic sets: Applications of graph convexity to genome rearrangement problems. Electron. Notes Discrete Math. 69, 285–292.

Eriksson

, Eriksson

, Karlander

, et al. 2001. Sorting a bridge hand. Discrete Math. 241, 289–300.

Feijao

, and Meidanis

2011. SCJ: A breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans. Comput. Biol. Bioinform. 8, 1318–1329.

Fertin

, Labarre

, Rusu

, et al. 2009. Combinatorics of Genome Rearrangements. The MIT Press, Cambridge, MA.

10.

Friedberg

, Darling

A.E.

, and Yancopoulos

2008. Genome rearrangement by the double cut and join operation. Methods Mol Biol. 452, 385–416.

11.

Haghighi

, and Sankoff

2012. Medians seek the corners, and other conjectures. BMC Bioinformatics. 13, S5.

12.

Irizarry

, Merriman

, Bahamonde

, et al. 2005. The evolution of signaling complexity suggests a mechanism for reducing the genomic search space in human association studies. Mol. Psychiatry. 10, 14–26.

13.

Konstantinova

2008. Some problems on Cayley graphs. Linear Algebra Appl. 429, 2754–2769.

14.

Lanctot

J.K.

, Li

, Ma

, et al. 2003. Distinguishing string selection problems. Inf. Comput. 185, 41–55.

15.

Langfelder

, Mischel

P.S.

, and Horvath

2013. When is hub gene selection better than standard meta-analysis?. PLoS One. 8, e61505.

16.

, Lai

, and Zhong

2004. [Introduction to the methods of constructing phylogenetic trees with DNA sequences]. Yi Chuan. 26, 205–210.

17.

Penso

L.D.

, Protti

, Rautenbach

, et al. 2015. Complexity analysis of P₃-convexity problems on bounded-degree and planar graphs. Theor. Comput. Sci. 607, 83–95.

18.

Pe'er

, and Shamir

1998. The median problems for breakpoints are NP-complete. Elec. Colloq. Comput. Complexity. 71, 1–16.

19.

Popov

V.Y.

2007. Multiple genome rearrangement by swaps and by element duplications. Theor. Comput. Sci. 385, 115–126.

20.

Sankoff

, and Blanchette

1998. Multiple genome rearrangement and breakpoint phylogeny. J. Comput. Biol. 5, 555–570.

21.

Zanetti

J.P.P.

, Biller

, and Meidanis

2013. On the matrix median problem, 230–243. In International Workshop on Algorithms in Bioinformatics. Springer-Verlag, New York, NY.