Search

In this paper, we determine the computational complexity of recognizing two graph classes, \emph{grounded L}-graphs and \emph{stabbable grid intersection} graphs. An L-shape is made by joining the bottom end-point of a vertical ($\vert$) segment to the left end-point of a horizontal ($-$) segment. The top end-point of the vertical segment is known as the {\em anchor} of the L-shape. Grounded L-graphs are the intersection graphs of L-shapes such that all the L-shapes' anchors lie on the same horizontal line. We show that recognizing grounded L-graphs is NP-complete. This answers an open question asked by Jel{\'\i}nek \& T{\"o}pfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line $\ell$ stabs a segment $s$, if $s$ intersects $\ell$. A graph $G$ is a stabbable grid intersection graph ($StabGIG$) if there is a grid intersection representation of $G$ in which the same line stabs all its segments. We show that recognizing $StabGIG$ graphs is $NP$-complete, even on a restricted class of graphs. This answers an open question asked by Chaplick \etal (\textsc{O}rder, 2018)., Comment: 18 pages, 11 Figures

Stick graphs are defined as follows. Let A (respectively B) be a set of vertical (respectively horizontal) segments in the plane such that the bottom endpoints of the segments in A and the left endpoints of the segments in B lie on the same ground straight line with slope -1. The Stick graph defined by A and B, which is necessarily bipartite, is the intersection graph of the segments in A with the segments in B. We answer an open problem by showing that recognizing Stick graphs is NP-complete. This result allows us to easily solve two other open problems, namely the recognition of BipHook graphs and of max point-tolerance graphs. We show that both of them are NP-complete problems., Comment: 24 pages, 12 figures

We provide new interpretations for a subset of Raney numbers, involving threshold sequences and Motzkin-like paths with long up and down steps. Given three integers n, k, l such that n >= 1, k >= 2 and 0 <= l <= k-2, a (k,l)-threshold sequence of length n is any strictly increasing sequence S=(s_1 s_2 ... s_n) of integers such that ki <= s_i <= kn+l. These sequences are in bijection with ordered (l+1)-tuples of k-ary trees. We prove this result and identify the Raney numbers that count the (k,l)-threshold sequences. As a consequence, when k=2 and k=3, we deduce combinatorial identities involving Catalan numbers and powers of 2, and respectively Fuss-Catalan and Raney numbers. Finally, we show how to represent threshold sequences as Motzkin-like paths with long up and down steps, and deduce that these paths are enumerated by the same Raney numbers., Comment: 16 pages, 4 figures

A Stick graph G=(A\cup B, E) is the intersection graph of a set A of horizontal segments and a set B of vertical segments in the plane, whose left and respectively bottom endpoints lie on the same ground line with slope -1. These endpoints are respectively called A-origins and B-origins. When a total order is provided for the A-origins, the resulting graphs are called A-Stick graphs. In this paper, we propose a characterization of the class of A-Stick graphs using forced pairs, which are pairs of segments in B with the property that only one left-to-right order of their origins is possible on the ground line. We deduce a recognition algorithm for A-Stick graphs running in O(|A|+|B|+|E|) time, thus improving the running time of O(|A|\cdot |B|) of the best current algorithm. We also introduce the problem of finding, for a Stick graph, a representation using segments of minimum total length. The canonical order on the A- and B-origins, output by our recognition algorithm, allows us to obtain partial results on this problem., Comment: 26 pages, 3 figures

Grid intersection graphs are the intersection graphs of vertical and horizontal segments in the plane. When the bottom and respectively left endpoints of the vertical and horizontals segments belong to a line with negative slope, the graph is called a Stick graph. Very few results exist on Stick graphs: only small classes of Stick graphs have been identified; recognizing Stick graphs is an open problem; and even building examples of graphs that are not Stick graphs is quite tricky. In this paper, we first prove that the complements of circle graphs and of circular arc graphs are Stick graphs. Then, we propose two certificates allowing to decide that a graph is not a Stick graph, and use them to build new examples of non-Stick graphs. It turns out that these examples of non-Stick graphs, as well as all those from literature, have long holes. We thus also investigate the place of chordal grid intersection graphs in the hierarchy of classes built around Stick graphs., Comment: 15 pages, 5 figures

We give a positive answer to a question raised by Davis et al. ({\em Discrete Mathematics} 341, 2018), concerning permutations with the same pinnacle set. Given $\pi\in S_n$, a {\em pinnacle} of $\pi$ is an element $\pi_i$ ($i\neq 1,n$) such that $\pi_{i-1}<\pi_i>\pi_{i+1}$. The question is: given $\pi,\pi'\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $\pi$ into $\pi'$ such that all the intermediate permutations have pinnacle set $S$? We introduce {\em balanced reversals}, defined as reversals that do not modify the pinnacle set of the permutation to which they are applied. Then we show that $\pi$ may be sorted by balanced reversals (i.e. transformed into a standard permutation $\Id_S$), implying that $\pi$ may be transformed into $\pi'$ using at most $4n-2\min\{p,3\}$ balanced reversals, where $p=|S|\geq 1$. In case $p=0$, at most $2n-1$ balanced reversals are needed., Comment: 18 pages, 1 figure

A pinnacle of a permutation is a value that is larger than its immediate neighbors when written in one-line notation. In this paper, we build on previous work that characterized admissible pinnacle sets of permutations. For these sets, there can be specific orderings of the pinnacles that are not admissible, meaning that they are not realized by any permutation. Here we characterize admissible orderings, using the relationship between a pinnacle x and its rank in the pinnacle set to bound the number of times that the pinnacles less than or equal to x can be interrupted by larger values., Comment: to appear in Graphs and Combinatorics

In directed graphs, we investigate the problems of finding: 1) a minimum feedback vertex set (also called the Feedback Vertex Set problem, or MFVS), 2) a feedback vertex set inducing an acyclic graph (also called the Vertex 2-Coloring without Monochromatic Cycles problem, or Acyclic FVS) and 3) a minimum feedback vertex set inducing an acyclic graph (Acyclic MFVS). We show that these problems are strongly related to (variants of) Monotone 3-SAT and Monotone NAE 3-SAT, where monotone means that all literals are in positive form. As a consequence, we deduce several NP-completeness results on restricted versions of these problems. In particular, we define the 2-Choice version of an optimization problem to be its restriction where the optimum value is known to be either D or D+1 for some integer D, and the problem is reduced to decide which of D or D+1 is the optimum value. We show that the 2-Choice versions of MFVS, Acyclic MFVS, Min Ones Monotone 3-SAT and Min Ones Monotone NAE 3-SAT are NP-complete. The two latter problems are the variants of Monotone 3-SAT and respectively Monotone NAE 3-SAT requiring that the truth assignment minimize the number of variables set to true. Finally, we propose two classes of directed graphs for which Acyclic FVS is polynomially solvable, namely flow reducible graphs (for which MFVS is already known to be polynomially solvable) and C1P-digraphs (defined by an adjacency matrix with the Consecutive Ones Property).

Let $S=\{K_{1,3},K_3,P_4\}$ be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph $G$ into graphs taken from any non-empty $S'\subseteq S$. The problem is known to be NP-complete for any possible choice of $S'$ in general graphs. In this paper, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of $S'$. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterisations of $S'$-decomposable cubic graphs in some cases., Comment: to appear in the proceedings of COCOON 2016

Link-cut trees have been introduced by D.D. Sleator and R.E. Tarjan (Journal of Computer and System Sciences, 1983) with the aim of efficiently maintaining a forest of vertex-disjoint dynamic rooted trees under cut and link operations. These operations respectively disconnect a subtree from a tree, and join two trees by an edge. Additionally, link-cut trees allow to change the root of a tree and to perform a number of updates and queries on cost values defined on the arcs of the trees. All these operations are performed in $O(\log\, n)$ amortized or worst-case time, depending on the implementation, where $n$ is the total size of the forest. In this paper, we show that a list of elements implemented using link-cut trees (we call it a $\log$-list) allows us to obtain a common running time of $O(\log\, n)$ for the classical operations on lists, but also for some other essential operations that usually take linear time on lists. Such operations require to find the minimum/maximum element in a sublist defined by its endpoints, the position of a given element in the list or the element placed at a given position in the list; or they require to add a value $a$, or to multiply by $-1$, all the elements in a sublist. Furthermore, we use $\log$-lists to implement several existing algorithms for sorting permutations by transpositions and/or reversals and/or block-interchanges, and obtain $O(n\,\log\, n)$ running time for all of them. In this way, the running time of several algorithms is improved, whereas in other cases our algorithms perform as well as the best existing implementations., Comment: 19 pages, 7 figures

In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, several sortedness constraints have been defined, for which propagation algorithms are available, but for which the tractability is not settled. We show that the sort(U,V) constraint (Older et. al, 1995) is intractable for integer variables whose domains are not limited to intervals. As a consequence, the similar result holds for the sort(U,V, P) constraint (Zhou, 1996). Moreover, the intractability holds even under the stability condition present in the recently introduced keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014), and requiring that the order of the variables with the same value in the list U be preserved in the list V. Therefore, keysorting(U,V,Keys,P) is intractable as well., Comment: 15 pages, 4 figures

In this paper, we investigate the reconstruction of permutations on {1, 2, ..., n} from betweenness constraints involving the minimum and the maximum element located between t and t+1, for all t=1, 2, ..., n-1. We propose two variants of the problem (directed and undirected), and focus first on the directed version, for which we draw up general features and design a polynomial algorithm in a particular case. Then, we investigate necessary and sufficient conditions for the uniqueness of the reconstruction in both directed and undirected versions, using a parameter k whose variation controls the stringency of the betweenness constraints. We finally point out open problems., Comment: 16 pages, 3 figures

Common intervals have been defined as a modelisation of gene clusters in genomes represented either as permutations or as sequences. Whereas optimal algorithms for finding common intervals in permutations exist even for an arbitrary number of permutations, in sequences no optimal algorithm has been proposed yet even for only two sequences. Surprisingly enough, when sequences are reduced to permutations, the existing algorithms perform far from the optimum, showing that their performances are not dependent, as they should be, on the structural complexity of the input sequences. In this paper, we propose to characterize the structure of a sequence by the number $q$ of different dominating orders composing it (called the domination number), and to use a recent algorithm for permutations in order to devise a new algorithm for two sequences. Its running time is in $O(q_1q_2p+q_1n_1+q_2n_2+N)$, where $n_1, n_2$ are the sizes of the two sequences, $q_1,q_2$ are their respective domination numbers, $p$ is the alphabet size and $N$ is the number of solutions to output. This algorithm performs better as $q_1$ and/or $q_2$ reduce, and when the two sequences are reduced to permutations (i.e. when $q_1=q_2=1$) it has the same running time as the best algorithms for permutations. It is also the first algorithm for sequences whose running time involves the parameter size of the solution. As a counterpart, when $q_1$ and $q_2$ are of $O(n_1)$ and $O(n_2)$ respectively, the algorithm is less efficient than other approaches., Comment: 22 pages

Motivated by the study of genome rearrangements, the NP-hard Minimum Common String Partition problems asks, given two strings, to split both strings into an identical set of blocks. We consider an extension of this problem to unbalanced strings, so that some elements may not be covered by any block. We present an efficient fixed-parameter algorithm for the parameters number k of blocks and maximum occurrence d of a letter in either string. We then evaluate this algorithm on bacteria genomes and synthetic data., Comment: Peer-reviewed and presented as part of the 13th Workshop on Algorithms in Bioinformatics (WABI2013)

In this paper we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or a common (resp. conserved) interval that contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the classical notion of nested interval. We exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. We also explain how to count all b-nested intervals in O(Kn) time. New properties of the family of conserved intervals are proposed to do so.

Common intervals of K permutations over the same set of n elements were firstly investigated by T. Uno and M.Yagiura (Algorithmica, 26:290:309, 2000), who proposed an efficient algorithm to find common intervals when K=2. Several particular classes of intervals have been defined since then, e.g. conserved intervals and nested common intervals, with applications mainly in genome comparison. Each such class, including common intervals, led to the development of a specific algorithmic approach for K=2, and - except for nested common intervals - for its extension to an arbitrary K. In this paper, we propose a common and efficient algorithmic framework for finding different types of common intervals in a set P of K permutations, with arbitrary K. Our generic algorithm is based on a global representation of the information stored in P, called the MinMax-profile of P, and an efficient data structure, called an LR-stack, that we introduce here. We show that common intervals (and their subclasses of irreducible common intervals and same-sign common intervals), nested common intervals (and their subclass of maximal nested common intervals) as well as conserved intervals (and their subclass of irreducible conserved intervals) may be obtained by appropriately setting the parameters of our algorithm in each case. All the resulting algorithms run in O(Kn+N)-time and need O(n) additional space, where N is the number of solutions. The algorithms for nested common intervals and maximal nested common intervals are new for K>2, in the sense that no other algorithm has been given so far to solve the problem with the same complexity, or better. The other algorithms are as efficient as the best known algorithms., Comment: 25 pages, 2 figures

Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP-hard, thus answering the long-standing question of its computational complexity., Comment: Corrected references

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the Sorting by Transpositions problem, has been introduced by Bafna and Pevzner in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is NP-hard. As a corollary of our result, we also prove that the following problem is NP-hard: given a permutation pi, is it possible to sort pi using db(pi)/3 permutations, where db(pi) is the number of breakpoints of pi?

A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogeny. All the existing measures are defined on genomes without duplicates. However, we know that genes can be duplicated within the same genome. One possible approach to overcome this difficulty is to establish a one-to-one correspondence (i.e. a matching) between genes of both genomes, where the correspondence is chosen in order to optimize the studied measure. In this paper, we are interested in three measures (number of breakpoints, number of common intervals and number of conserved intervals) and three models of matching (exemplar, intermediate and maximum matching models). We prove that, for each model and each measure M, computing a matching between two genomes that optimizes M is APX-hard. We also study the complexity of the following problem: is there an exemplarization (resp. an intermediate/maximum matching) that induces no breakpoint? We prove the problem to be NP-Complete in the exemplar model for a new class of instances, and we show that the problem is in P in the maximum matching model. We also focus on a fourth measure: the number of adjacencies, for which we give several approximation algorithms in the maximum matching model, in the case where genomes contain the same number of duplications of each gene.