Search

Let S={K1,3,K3,P4} 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 nonempty S′⊆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 subcubic (i.e., all its vertices have degree at most 3), 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. [ABSTRACT FROM AUTHOR]

Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content of diploid genomes to be used as basis of sequence analysis. In this paper, we show that the computational complexity will change for natural extensions of alignments to pan-genome representations and to diploid genomes. More broadly, our approach can also be seen as a minimal extension of sequence alignment to labelled directed acyclic graphs (labeled DAGs). Namely, we show that finding a covering alignment of two labeled DAGs is NP-hard even on binary alphabets. A covering alignment asks for two paths $R_1$ (red) and $G_1$ (green) in DAG $D_1$ and two paths $R_2$ (red) and $G_2$ (green) in DAG $D_2$ that cover the nodes of the graphs and maximize the sum of the global alignment scores: $\mathsf {as}(\mathsf {sp}(R_1),\mathsf {sp}(R_2))+\mathsf {as}(\mathsf {sp}(G_1),\mathsf {sp}(G_2))$ , where $\mathsf {sp}(P)$ is the concatenation of labels on the path $P$ . Pair-wise alignment of haplotype sequences forming a diploid chromosome can be converted to a two-path coverable labelled DAG, and then the covering alignment models the similarity of two diploids over arbitrary recombinations. We also give a reduction to the other direction, to show that such a recombination-oblivious diploid alignment is NP-hard on alphabets of size 3. [ABSTRACT FROM AUTHOR]

Conditional Simple Temporal Network (CSTN ) is a constraint-based graph formalism for conditional temporal planning, which may be viewed as an extension of Simple Temporal Networks. Recently, STN s have been generalized into Hyper Temporal Networks (HyTN s), by considering weighted directed hypergraphs where each hyperarc models a disjunctive temporal constraint. We introduce the Conditional Hyper Temporal Network (CHyTN) model, a natural extension and generalization of both CSTN s and HyTN s, obtained by blending them together. We show that deciding whether a given CSTN is dynamically-consistent is coNP -hard, and that deciding whether a given CHyTN is dynamically-consistent is PSPACE -hard. Next, we offer the first deterministic (pseudo) singly-exponential time algorithm for checking DC in CHyTNs and CSTN s. To analyze the computational complexity of the proposed algorithm, we introduce a refined notion of DC, named ϵ-DC , presenting a sharp lower bounding analysis on the critical value of the reaction time where a conditional temporal network transits from being, to not being, dynamically-consistent. [ABSTRACT FROM AUTHOR]

In the Train Marshalling Problem (TMP) the cars of a train having different destinations have to be reordered in such a way that all the cars with the same destination appear consecutively. To this aim the cars are first shunted on k auxiliary rails, then the sequences of cars present on the different rails are reconnected one after the other to form a new train. The TMP is the problem of minimizing the number k of auxiliary rails needed to obtain a train with the required property. The TMP is an NP-hard problem. Here we present an exact dynamic programming algorithm for the TMP based on the inclusion–exclusion principle. The algorithm has polynomial space complexity and time complexity that is polynomial in the number of cars, exponential in the number of destinations. This shows that the TMP is fixed parameter tractable with the number of destinations as parameter. [ABSTRACT FROM AUTHOR]

Let B be a positive integer and let G be a simple graph. An excessive [ B]-factorization of G is a minimum set of matchings, each of size B, whose union is [ABSTRACT FROM AUTHOR]

A graph G is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional. Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the central problem of finding recombination events. It is commonly assumed that a present population is a descendent of a small number of specific sequences called founders. The recombination process consists in given two equal length sequences, generates a third sequence of the same length by concatenating the prefix of one sequence with the suffix of the other sequence. Due to recombination, a present sequence (called a recombinant) is thus composed of blocks from the founders. A major question related to founder sequences is the so-called MINIMUM MOSAIC problem: using the natural parsimony criterion for the number of recombinations, find the "best" founders. In this article, we prove that the MINIMUM MOSAIC problem given haplotype recombinants with no missing values is NP-hard when the number of founders is given as part of the input and propose some exact exponential-time algorithms for the problem, which can be considered polynomial provided some extra information. Notice that Rastas and Ukkonen proved that the MINIMUM MOSAIC problem is NP-hard using a somewhat unrealistic mutation cost function. The aim of this paper is to provide a better complexity insight of the problem. [ABSTRACT FROM AUTHOR]

Abstract: In the context of comparative analysis of protein–protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein–protein interaction graph (target graph) of another species with respect to (w.r.t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively. [Copyright &y& Elsevier]

Abstract: Cycles in graphs play an important role in many applications, e.g., analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. From a mathematical point of view, cycles in graphs have a rich structure. Cycle bases are a compact description of the set of all cycles of a graph. In this paper, we survey the state of knowledge on cycle bases and also derive some new results. We introduce different kinds of cycle bases, characterize them in terms of their cycle matrix, and prove structural results and a priori length bounds. We provide polynomial algorithms for the minimum cycle basis problem for some of the classes and prove -hardness for others. We also discuss three applications and show that they require different kinds of cycle bases. [Copyright &y& Elsevier]

Abstract: In the context of comparative analysis of protein–protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the protein–protein interaction graph H of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the Exact--Matching problem and the Max--Matching problems, where (resp. ) denotes in both problems the maximum number of orthologous proteins in H (resp. G) of a protein in G (resp. H). Following [I. Fagnot, G. Lelandais, S. Vialette, Bounded list injective homomorphism for comparative analysis of protein–protein interaction graphs, Journal of Discrete Algorithms 6 (2) (2008) 178–191], the Exact--Matching problem asks for an injective homomorphism of G to H w.r.t. orthologous proteins. The optimization version is called the Max--Matching problem and is concerned with finding an injective mapping of a graph G to a graph H w.r.t. orthologous proteins that matches as many edges of G as possible. For both problems, we essentially focus on bounded degree graphs and extremal small values of parameters and . [Copyright &y& Elsevier]

Abstract: The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. Recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced, where the goal is to find all pre-duplications, that is duplications that in the evolution precede the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite. First of all, we prove that the Minimum Duplication problem is -hard, even when the input consists of five uniquely leaf-labeled gene trees (improving upon known results on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently with a randomized algorithm when the input gene trees have bounded depth. An extended abstract of this paper appeared in SOFSEM 2012 [1]. [Copyright &y& Elsevier]

Abstract: We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two. [Copyright &y& Elsevier]