Cut arcs , or strong bridges , are one of the most fundamental reachability notions in directed graphs. Specifically, in a strongly connected graph \(G=(V,E)\) ( \(|V|=n\) , \(|E|=m\) ), a cut arc is an arc \(e\in E\) for which there exist \(u,v\in V\) , such that all \( u \) - \( v \) walks contain \( e \) . In this article, we generalise this notion to cut paths , that is, walks \( W \) for which there exist \(u,v\in V\) , such that all \( u \) - \( v \) walks contain \( W \) as subwalk. We first prove various properties of cut paths and define their remainder structure , which we use to present a simple \(O(m)\) -time verification algorithm for a cut path. We further show that a graph contains at most \(O(n)\) maximal cut paths of length at most \(O(n)\) each, and present an optimal \(O(n^{2})\) enumeration algorithm for maximal cut paths. We apply cut paths and their remainder structure to improve several reachability problems from bioinformatics, as follows. A walk is called safe if it is a subwalk of every node-covering closed walk of a strongly connected graph. Multi-safety is defined analogously, by considering node-covering sets of closed walks instead. Cut paths provide simple \(O(m)\) -time algorithms verifying if a walk is safe or multi-safe. Further, by simultaneous computation of remainder structures of all subwalks of a cut path in linear time, we can identify all maximal multi-safe walks in \(O(mn)\) time. This improves over the state-of-the-art algorithm running in time \(O(m^{2}+n^{3}\log n)\) .

A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionally they are optimal with respect to some function. In this paper we study safe sequences of nodes or arcs, namely sequences that appear in some path of every path cover of a DAG. We show that safe sequences admit a simple characterization via cutnodes. Moreover, we establish a connection between maximal safe sequences and leaf-to-root paths in the source- and sink-dominator trees of the DAG, which may be of independent interest in the extensive literature on dominators. With dominator trees, safe sequences admit an O(n)-size representation and a linear-time output-sensitive enumeration algorithm running in time O(m + o), where n and m are the number of nodes and arcs, respectively, and o is the total length of the maximal safe sequences. We then apply maximal safe sequences to simplify Integer Linear Programs (ILPs) for two path-covering problems, LeastSquares and MinPathError, which are at the core of RNA transcript assembly problems from bioinformatics. On various datasets, maximal safe sequences can be computed in under 0.1 seconds per graph, on average, and ILP solvers whose search space is reduced in this manner exhibit significant speed-ups. For example on graphs with a large width, average speed-ups are in the range 50-250× for MinPathError and in the range 80-350× for LeastSquares. Optimizing ILPs using safe sequences can thus become a fast building block of practical RNA transcript assembly tools, and more generally, of path-covering problems.

Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A d -interval is the union of d disjoint intervals on the real line, and a graph is a d -interval graph if it is the intersection graph of d -intervals. In particular, it is a unit d -interval graph if it admits a d -interval representation where every interval has unit length. Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes such as 2-track interval graphs is NP -complete, the complexity of recognizing unit 2-interval graphs remains open. Here, we settle this question by proving that the recognition of unit 2-interval graphs is also NP -complete. Our proof technique uses a completely different approach from the other hardness results of recognizing related classes. Furthermore, we extend the result for unit d -interval graphs for any d ≥ 2 , which does not follow directly in graph recognition problems — as an example, it took almost 20 years to close the gap between d = 2 and d > 2 for the recognition of d -track interval graphs. Our result has several implications, including that for every d ≥ 2 , recognizing ( x , … , x ) d -interval graphs and depth r unit d -interval graphs is NP -complete for every x ≥ 11 and every r ≥ 4 .

Business Process Compliance is a family of methods to evaluate Business Processes in terms of the existence of one execution (one trace) that does not violate constraints superimposed on the process itself. The dual version is formulated as the superimposition of a set of constraints and consequent evaluation of the process for all the executions . These problems are relevant to a large part of actual applications, especially those in the context of regulatory compliance where we aim at verifying the process against a normative background (including, for instance, soft ones, such as guidelines, product specification, and product standards) or goals fixed by the owner of the process. In this paper we discuss one new type of compliance, that is impact compliance , devised to verify when a process respects a set of constraints, to establish that certain amounts, measuring the undesired effects of the tasks executed to implement the process, are below given limits . In the current literature on Business Process Management, Business Process Analysis, and Business Process Compliance, this type of compliance checking process has not yet been addressed. As we demonstrate in this paper, this problem is significant and complex to address. In particular, we show that the checking problems described above are, under certain structural conditions, polynomially solvable on deterministic machines. In general, however, the first problem is NP-complete whilst the second is polynomially solvable on deterministic machines.

In the structure from motion, the viewing graph is a graph where the vertices correspond to cameras (or images) and the edges represent the fundamental matrices. We provide a new formulation and an algorithm for determining whether a viewing graph is solvable, i.e., uniquely determines a set of projective cameras. The known theoretical conditions either do not fully characterize the solvability of all viewing graphs, or are extremely difficult to compute because they involve solving a system of polynomial equations with a large number of unknowns. The main result of this paper is a method to reduce the number of unknowns by exploiting cycle consistency. We advance the understanding of solvability by (i) finishing the classification of all minimal graphs up to 9 nodes, (ii) extending the practical verification of solvability to minimal graphs with up to 90 nodes, (iii) finally answering an open research question by showing that finite solvability is not equivalent to solvability, and (iv) formally drawing the connection with the calibrated case (i.e., parallel rigidity). Finally, we present an experiment on real data that shows that unsolvable graphs may appear in practice.

For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1,2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2.

In this paper, we propose a methodology for deriving a new kind of approximate temporal functional dependencies, called Approximate Predictive Functional Dependencies (APFDs), based on a three-window framework and on a multi-temporal relational model. Different features are proposed for the Observation Window (OW), where we observe predictive data, for the Waiting Window (WW), and for the Prediction Window (PW), where the predicted event occurs. We then consider the concept of approximation for such APFDs, introduce new error measures, and discuss different strategies for deriving APFDs. We discuss the quality, i.e., the informative content, of the derived AFDs by considering their entropy and information gain. Moreover, we outline the results in deriving APFDs focusing on the Acute Kidney Injury (AKI). We use real clinical data contained in the MIMIC III dataset related to patients from Intensive Care Units to show the applicability of our approach to real-world data.

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation X on a directed graph G into weighted source-to-sink paths whose weighted sum equals X . We show that, for acyclic graphs, considering the width of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of width-stable graphs, for which a popular heuristic is a O (log Val ( X ))-approximation ( Val ( X ) being the total flow of X ), and strengthen its worst-case approximation ratio from \(\Omega (\sqrt {m})\) to Ω ( m /log m ) for sparse graphs, where m is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖ X ‖ being the maximum absolute value of X on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖ X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ 2018 ], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths ( unitigs ) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks ( omnitigs ), thus giving the first safe and complete genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et al. (ACM Trans. Algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m) -time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ (mn) total maximal omnitig size. This is based on the discovery of a family of walks ( macrotigs ) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m) -time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and complete genome assembly programs, as has been the case for other key Bioinformatics problems.

Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A $d$-interval is the union of $d$ intervals on the real line, and a graph is a $d$-interval graph if it is the intersection graph of $d$-intervals. In particular, it is a unit $d$-interval graph if it admits a $d$-interval representation where every interval has unit length. Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes such as 2-track interval graphs is NP-complete, the complexity of recognizing unit 2-interval graphs remains open. Here, we settle this question by proving that the recognition of unit 2-interval graphs is also NP-complete. Our proof technique uses a completely different approach from the other hardness results of recognizing related classes. Furthermore, we extend the result for unit $d$-interval graphs for any $d\geq 2$, which does not follow directly in graph recognition problems --as an example, it took almost 20 years to close the gap between $d=2$ and $d> 2$ for the recognition of $d$-track interval graphs. Our result has several implications, including that recognizing $(x, \dots, x)$ $d$-interval graphs and depth $r$ unit 2-interval graphs is NP-complete for every $x\geq 11$ and every $r\geq 4$.

In a strongly connected graph $G = (V,E)$, a cut arc (also called strong bridge) is an arc $e \in E$ whose removal makes the graph no longer strongly connected. Equivalently, there exist $u,v \in V$, such that all $u$-$v$ walks contain $e$. Cut arcs are a fundamental graph-theoretic notion, with countless applications, especially in reachability problems. In this paper we initiate the study of cut paths, as a generalisation of cut arcs, which we naturally define as those paths $P$ for which there exist $u,v \in V$, such that all $u$-$v$ walks contain $P$ as subwalk. We first prove various properties of cut paths and define their remainder structures, which we use to present a simple $O(m)$-time verification algorithm for a cut path ($|V| = n$, $|E| = m$). Secondly, we apply cut paths and their remainder structures to improve several reachability problems from bioinformatics. A walk is called safe if it is a subwalk of every node-covering closed walk of a strongly connected graph. Multi-safety is defined analogously, by considering node-covering sets of closed walks instead. We show that cut paths provide simple $O(m)$-time algorithms verifying if a walk is safe or multi-safe. For multi-safety, we present the first linear time algorithm, while for safety, we present a simple algorithm where the state-of-the-art employed complex data structures. Finally we show that the simultaneous computation of remainder structures of all subwalks of a cut path can be performed in linear time. These properties yield an $O(mn)$ algorithm outputting all maximal multi-safe walks, improving over the state-of-the-art algorithm running in time $O(m^2+n^3)$. The results of this paper only scratch the surface in the study of cut paths, and we believe a rich structure of a graph can be revealed, considering the perspective of a path, instead of just an arc.

Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation $X$ on a directed graph $G$ into weighted source-to-sink paths whose superposition equals $X$. We show that, for acyclic graphs, considering the \emph{width} of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of \emph{width-stable} graphs, for which a popular heuristic is a \gwsimple-approximation ($|X|$ being the total flow of $X$), and strengthen its worst-case approximation ratio from $Ω(\sqrt{m})$ to $Ω(m / \log m)$ for sparse graphs, where $m$ is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation ($\Vert X \Vert$ being the maximum absolute value of $X$ on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations ($\Vert X \Vert \leq 1$), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [ALENEX 2018], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version.

A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V, E) is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size k of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose running time is parameterized on k. We obtain two new MPC parameterized algorithms for DAGs running in time O(k2|V| log |V| + |E|) and O(k3|V| + |E|). We also obtain a parallel algorithm running in O(k2|V| + |E|) parallel steps and using O(log |V|) processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we show that we can transform (in O(k2|V|) time) a given MPC into another MPC that uses less than 2|V| distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.

Abstract Given a directed graphGand a pair of nodessandt, ans-tbridgeofGis an edge whose removal breaks alls-tpaths ofG(and thus appears in alls-tpaths). Computing alls-tbridges ofGis a basic graph problem, solvable in linear time. In this paper, we consider a natural generalisation of this problem, with the notion of “safety” from bioinformatics. We say that a walkWissafewith respect to a set $${\mathcal {W}}$$ W ofs-twalks, ifWis a subwalk of all walks in $${\mathcal {W}}$$ W . We start by considering the maximal safe walks when $${\mathcal {W}}$$ W consists of: alls-tpaths, alls-ttrails, or alls-twalks ofG. We show that the solutions for the first two problems immediately follow from finding alls-tbridges after incorporating simple characterisations. However, solving the third problem requires non-trivial techniques for incorporating its characterisation. In particular, we show that there exists a compact representation computable in linear time, that allows outputting all maximal safe walks in time linear in their length. Our solutions also directly extend to multigraphs, except for the second problem, which requires a more involved approach. We further generalise these problems, by assuming that safety is defined only with respect to a subset ofvisibleedges. Here we prove a dichotomy between thes-tpaths ands-ttrails cases, and thes-twalks case: the former two are NP-hard, while the latter is solvable with the same complexity as when all edges are visible. We also show that the same complexity results hold for the analogous generalisations ofs-tarticulation points(nodes appearing in alls-tpaths). We thus obtain the best possible results for natural “safety”-generalisations of these two fundamental graph problems. Moreover, our algorithms are simple and do not employ any complex data structures, making them ideal for use in practice.

A multi-assembly problem asks to reconstruct multiple genomic sequences from mixed reads sequenced from all of them. Standard formulations of such problems model a solution as a path cover in a directed acyclic graph, namely a set of paths that together cover all vertices of the graph. Since multi-assembly problems admit multiple solutions in practice, we consider an approach commonly used in standard genome assembly: output only partial solutions (contigs, or safe paths), that appear in all path cover solutions. We study constrained path covers, a restriction on the path cover solution that incorporate practical constraints arising in multi-assembly problems. We give efficient algorithms finding all maximal safe paths for constrained path covers. We compute the safe paths of splicing graphs constructed from transcript annotations of different species. Our algorithms run in less than 15 seconds per species and report RNA contigs that are over 99% precise and are up to 8 times longer than unitigs. Moreover, RNA contigs cover over 70% of the transcripts and their coding sequences in most cases. With their increased length to unitigs, high precision, and fast construction time, maximal safe paths can provide a better base set of sequences for transcript assembly programs.

In this paper we give a structural characterization and extend the tractability frontier of the Simple Temporal Problem (STP) by defining the class of the Extended Simple Temporal Problem (ESTP), which augments STP with strict inequalities and monotone Boolean formulae on inequations (i.e., formulae involving the operations of conjunction, disjunction and parenthesization). A polynomial-time algorithm is provided to solve ESTP, faster than previous state-of-the-art algorithms for other extensions of STP that had been considered in the literature, all encompassed by ESTP. We show the practical competitiveness of our approach through a proof-of-concept implementation and an experimental evaluation involving also state-of-the-art SMT solvers.

Games have a role in many aspects of science, technology, and society. Also, games attract humans' interest and offer unique learning opportunities. Indeed, the role of games in education has a long tradition. In this paper we introduce Code Colosseum, a platform that takes competitive programming in the direction of games, instead of problems. By taking this direction, we aim to create a more engaging environment for students to compete in. The platform allows programs written by the contestants to compete in a realtime multiplayer game. The platform also allows to spectate the matches between the programs. The design and implementation of Code Colosseum has been kept as simple as possible, to facilitate participation, maintenance and setup. To assess the effectiveness of the approach, we organized a tournament with 16 students, from both high schools and universities, as a pilot experience for Code Colosseum. In this tournament they created programs to play the Royal Game of Ur, a board racing game. The feedback from the students about the experience was positive, and the suggestions received will be implemented for future experiences.

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (omnitigs), thus giving the first safe and complete genome assembly algorithm. Even though omnitig finding was later improved to quadratic time, it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m)-time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and complete genome assembly programs, as has been the case for other key Bioinformatics problems.

Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G. Similarly, an s-t articulation point of G is a node whose removal breaks all s-t paths of G. Computing the sequence of all s-t bridges of G (as well as the s-t articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm (Ford and Fulkerson, 1956). We show a simplified and self-contained algorithm computing all s-t bridges and s-t articulation points of G, based on a single graph traversal from s to t avoiding an arbitrary s-t path, which is interrupted at the s-t bridges. Its proof of correctness uses simple inductive arguments, making the problem an application of merely graph traversal, rather than of the more complex maximum flow problem.

Extracting association rules from large datasets has been widely studied in many variants in the last two decades; they allow to extract relations between values that occur more “often” in a database. With temporal association rules the concept has been declined to temporal databases. In this context the “most frequent” patterns of evolution of one or more attribute values are extracted. In the temporal setting, especially where the interference betweeen temporal patterns cannot be neglected (e.g., in medical domains), there may be the case that we are looking for a set of temporal association rules for which a “significant” portion of the original database represents a consistent model for all of them. In this work, we introduce a simple and intuitive form for temporal association rules, called pure evolving association rules (PE-ARs for short), and we study the complexity of checking a set of PE-ARs over an instance of a temporal relation under approximation (i.e., a percentage of tuples that may be deleted from the original relation). As a by-product of our study we address the complexity class for a general problem on Directed Acyclic Graphs which is theoretically interesting per se.

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN by adding decision time points to model temporal plans with decisions. A decision time point is a special kind of time point that once executed allows for deciding a truth value for an associated Boolean proposition. Furthermore, STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i.e., complete truth value assignments to the propositions) they are relevant. Thus, an STND models a family of STNs each obtained as a projection of the initial STND onto a scenario. An STND is consistent if there exists a consistent scenario (i.e., a scenario such that the corresponding STN projection is consistent). Recently, a hybrid SAT-based consistency checking algorithm (HSCC) was proposed to check the consistency of an STND. Unfortunately, that approach lacks experimental evaluation and does not allow for the synthesis of all consistent scenarios. In this paper, we propose an incremental HSCC algorithm for STNDs that (i) is faster than the previous one and (ii) allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). Then, we carry out an experimental evaluation with KAPPA, a tool that we developed for STNDs. Finally, we prove that STNDs and disjunctive temporal networks (DTNs) are equivalent.

MOTIVATION: Discovering the evolution of a tumor may help identify driver mutations and provide a more comprehensive view on the history of the tumor. Recent studies have tackled this problem using multiple samples sequenced from a tumor, and due to clinical implications, this has attracted great interest. However, such samples usually mix several distinct tumor subclones, which confounds the discovery of the tumor phylogeny. RESULTS: We study a natural problem formulation requiring to decompose the tumor samples into several subclones with the objective of forming a minimum perfect phylogeny. We propose an Integer Linear Programming formulation for it, and implement it into a method called MIPUP. We tested the ability of MIPUP and of four popular tools LICHeE, AncesTree, CITUP, Treeomics to reconstruct the tumor phylogeny. On simulated data, MIPUP shows up to a 34% improvement under the ancestor-descendant relations metric. On four real datasets, MIPUP's reconstructions proved to be generally more faithful than those of LICHeE. AVAILABILITY AND IMPLEMENTATION: MIPUP is available at https://github.com/zhero9/MIPUP as open source. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w1,…,wn and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from Gopalan et al. (2011) [9], Štefankovič et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5]. Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

In this article, we consider the following problem. Given a directed graph G , output all walks of G that are sub-walks of all closed edge-covering walks of G . This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig . Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O ( nm )-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Ω( nm ). We implement this algorithm and show that it is 9--12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

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 acovering alignmentof 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.

International audience

Simple Temporal Networks (STNs) are a well-studied model for representing and reasoning about time. An STN comprises a set of real-valued variables called time-points, together with a set of binary constraints, each of the form Y <= X+w. The problem of finding a feasible schedule (i.e., an assignment of real numbers to time-points such that all of the constraints are satisfied) is equivalent to the Single Source Shortest Path problem (SSSP) in the STN graph. Simple Temporal Networks with Uncertainty (STNUs) augment STNs to include contingent links that can be used, for example, to represent actions with uncertain durations. The duration of a contingent link is not controlled by the planner, but is instead controlled by a (possibly adversarial) environment. Each contingent link has the form, , where 0 < l <= u < infty. Once the planner executes the activation time-point A, the environment must execute the contingent time-point C at some time A+Delta, where Delta in [l,u]. Crucially, the planner does not know the value of Delta in advance, but only discovers it when C executes. An STNU is dynamically controllable (DC) if there is a strategy that the planner can use to execute all of the non-contingent time-points, such that all of the constraints are guaranteed to be satisfied no matter which durations the environment chooses for the contingent links. The strategy can be dynamic in that it can react in real time to the contingent durations it observes. Recently, an upper bound of O(N^3) was given for the DC-checking problem for STNUs, where N is the number of time-points. This paper introduces a new algorithm, called the RUL^- algorithm, for solving the DC-checking problem for STNUs that improves on the O(N^3) bound. The worst-case complexity of the RUL^- algorithm is O(MN+K^2N+KN log N), where N is the number of time-points, M is the number of constraints, and K is the number of contingent time-points. If M is O(N^2), then the complexity reduces to O(N^3); however, in sparse graphs the complexity can be much less. For example, if M is O(N log N), and K is O(sqrt{N}), then the complexity of the RUL^- algorithm reduces to O(N^2 log N). The RUL^- algorithm begins by using the Bellman-Ford algorithm to compute a potential function. It then performs at most 2K rounds of computations, interleaving novel applications of Dijkstra's algorithm to (1) generate new edges and (2) update the potential function in response to those new edges. The constraint-propagation/edge-generation rules used by the RUL^- algorithm are distinguished from related work in two ways. First, they only generate unlabeled edges. Second, their applicability conditions are more restrictive. As a result, the RUL^- algorithm requires only O(K) rounds of Dijkstra's algorithm, instead of the O(N) rounds required by other approaches. The paper proves that the RUL^- algorithm is sound and complete for the DC-checking problem for STNUs.

In 2005 T.K.S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of temporal variables, and a finite set of temporal constraints each of which can be either one of the following three types: (t_1) two-variable linear-difference simple constraint; (t_2) single-variable disjunction of many interval constraints; (t_3) two-variable disjunction of two interval constraints only. Kumar showed that RDTPs are solvable in deterministic strongly polynomial time by reducing them to the Connected Row-Convex (CRC) constraints satisfaction problem, also devising a faster randomized algorithm. Instead, the most general form of DTPs allows for multi-variable disjunctions of many interval constraints and it is NP-complete. This work offers a deeper comprehension on the tractability of RDTPs, leading to an elementary deterministic strongly polynomial time algorithm for them, significantly improving the asymptotic running times of all the previous deterministic and randomized solutions. The result is obtained by reducing RDTPs to the Single-Source Shortest Paths (SSSP) and the 2-SAT problem (jointly), instead of reducing to CRCs. In passing, we obtain a faster (quadratic time) algorithm for RDTPs having only {t_1, t_2}-constraints and no t_3-constraint. As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a disjunctive strict generalization of Simple Temporal Networks (STNs) based on hypergraphs: we prove that solving temporal problems having only t_2-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in NP cap co-NP and admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only t_3-constraints and either only multi-tail or only multi-head hyperarc-constraints turns out strongly NP-complete.

Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, 2018) introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurović et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs. We give new, more transparent formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including (1) a strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth’s theorem, which may be of independent interest; (2) APX-hardness results for both problems; (3) approximation algorithms; and (4) exponential-time algorithms solving the two problems to optimality faster than the naïve brute-force approach. Our work relates to several well-studied notions in combinatorial optimization: chain partitions in partially ordered sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.

The amazing proliferation of communication technologies for embedded systems opens the way for completely new applications but forces designers to adopt new methodologies to meet time-to-market constraints. Computer-Aided Design (CAD) has been traditionally applied to computers and embedded systems in isolation without considering them as a global inter-connected system. The paper contributes to fill this gap by proposing 1) a communication-aware design flow for network-interconnected embedded systems and 2) a formal framework to efficiently synthesize their network aspects by formulating and solving an optimization problem. Presented case studies show the potentiality of the proposed approach to address heterogeneous scenarios, e.g., related to smart spaces up to the ever-more-mentioned Internet-of-Things.

Genome assembly is the problem of reconstructing a genome sequence from a set of reads from a sequencing experiment. Typical formulations of the assembly problem admit in practice many genomic reconstructions, and actual genome assemblers usually output contigs, namely substrings that are promised to occur in the genome. To bridge the theory and practice, Tomescu and Medvedev [RECOMB 2016] reformulated contig assembly as finding all substrings common to all genomic reconstructions. They also gave a characterization of those walks (omnitigs) that are common to all closed edge-covering walks of a (directed) graph, a typical notion of genomic reconstruction. An algorithm for listing all maximal omnitigs was also proposed, by launching an exhaustive visit from every edge. In this paper, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Omega(nm). We implement this algorithm and show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev [RECOMB 2016].

Computing the simulation preorder of a given Kripke structure (i.e., a directed graph with n labeled vertices) has crucial applications in model checking of temporal logic. It amounts to solving a specific two-players reachability game, called simulation game. We offer the first conditional lower bounds for this problem, and we relate its complexity (for computation, verification, and certification) to some variants of n × n matrix multiplication. We show that any O(na)-time algorithm for simulation games, even restricting to acyclic games/structures, can be used to compute n χ n boolean matrix multiplication (BMM) in O(nα) time. In the acyclic case, we match this bound by presenting the first subcubic algorithm, based on fast BMM, and running in nω +°(1) time (where ω < 2.376 is the exponent of matrix multiplication). For both acyclic and cyclic structures, we point out the existence of natural and canonical O(n2)-size certificates, that can be verified in truly subcubic time by means of matrix multiplication. In the acyclic case, O(n2) time is sufficient, employing standard (+, ×)-matrix product verification. In the cyclic case, a min-edge witness matrix multiplication (EWMM) is used, i.e., a matrix multiplication on the semi-ring (max, ×) where one matrix contains only 0's and 1's, which is computable in truly subcubic n(3+ω)/2+o(1) time. Finally, we show a reduction from EWMM to cyclic simulation games which implies a separation between the cyclic and the acyclic cases, unless EWMM can be verified in nω+°(1) time.

A Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network (STN) to include special time-points, called observation time-points. In a CSTN, the agent executing the network controls the execution of every time-point. However, each observation time-point has a unique propositional letter associated with it and, when the agent executes that time-point, the environment assigns a truth value to the corresponding letter. Thus, the agent observes but, does not control the assignment of truth values. A CSTN is dynamically consistent (DC) if there exists a strategy for executing its time-points such that all relevant constraints will be satisfied no matter which truth values the environment assigns to the propositional letters. Alternatively, in a Labeled Simple Temporal Network (Labeled STN) - also called a Temporal Plan with Choice - the agent executing the network controls the assignment of values to the so-called choice variables. Furthermore, the agent can make those assignments at any time. For this reason, a Labeled STN is equivalent to a Disjunctive Temporal Network. This paper incorporates both of the above extensions by augmenting a CSTN to include not only observation time-points but also decision time-points. A decision time-point is like an observation time-point in that it has an associated propositional letter whose value is determined when the decision time-point is executed. It differs in that the agent - not the environment - selects that value. The resulting network is called a CSTN with Decisions (CSTND). This paper shows that a CSTND generalizes both CSTNs and Labeled STNs, and proves that the problem of determining whether any given CSTND is dynamically consistent is PSPACE-complete. It also presents algorithms that address two sub-classes of CSTNDs: (1) those that contain only decision time-points; and (2) those in which all decisions are made before execution begins.

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN by adding decision time points to model temporal plans with decisions. A decision time point is a special kind of time point that once executed allows for deciding a truth value for an associated Boolean proposition. Furthermore, STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i.e., complete truth value assignments to the propositions) they are relevant. Thus, an STND models a family of STNs each obtained as a projection of the initial STND onto a scenario. An STND is consistent if there exists a consistent scenario (i.e., a scenario such that the corresponding STN projection is consistent). Recently, a hybrid SAT-based consistency checking algorithm (HSCC) was proposed to check the consistency of an STND. Unfortunately, that approach lacks experimental evaluation and does not allow for the synthesis of all consistent scenarios. In this paper, we propose an incremental HSCC algorithm for STNDs that (i) is faster than the previous one and (ii) allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). Then, we carry out an experimental evaluation with KAPPA, a tool that we developed for STNDs. Finally, we prove that STNDs and disjunctive temporal networks (DTNs) are equivalent.

Simple Temporal Networks with Uncertainty (STNUs) are a well-studied model for representing temporal constraints, where some intervals (contingent links) have an unknown but bounded duration, discovered only during execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the actual duration of contingent links revealed during execution. In this work we present a new system of constraint propagation rules for STNUs, which is sound-and-complete for DC checking. Our system comprises just three rules which, differently from the ones proposed in all previous works, only generate unconditioned constraints. In particular, after applying our sound rules, the network remains an STNU in all respects. Moreover, our completeness proof is short and non-algorithmic, based on the explicit construction of a valid execution strategy. This is a substantial simplification of the theory which underlies all the polynomial-time algorithms for DC-checking. Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of several variants of the notion of DC, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O(KN) total time in a network with K contingent links and N time points, considerably improving the previous O(N^3)-time bound.

In this paper, we present a novel algorithm for the maximum a posteriori decoding (MAPD) of time-homogeneous Hidden Markov Models (HMM), improving the worst-case running time of the classical Viterbi algorithm by a logarithmic factor. In our approach, we interpret the Viterbi algorithm as a repeated computation of matrix-vector (max, +)-multiplications. On time-homogeneous HMMs, this computation is online: a matrix, known in advance, has to be multiplied with several vectors revealed one at a time. Our main contribution is an algorithm solving this version of matrix-vector (max,+)-multiplication in subquadratic time, by performing a polynomial preprocessing of the matrix. Employing this fast multiplication algorithm, we solve the MAPD problem in O(mn2/log n) time for any time-homogeneous HMM of size n and observation sequence of length m, with an extra polynomial preprocessing cost negligible for m > n. To the best of our knowledge, this is the first algorithm for the MAPD problem requiring subquadratic time per observation, under the assumption — usually verified in practice — that the transition probability matrix does not change with time.

We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2 – ∊)-approximation of the diameter or a (5/3 – ∊)-approximation of all the eccentricities in O(m2–δ) time for any ∊, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 – 1/2k)-approximation of the diameter and the radius and a (3 – 4/(2k + 1))-approximation of all eccentricities in expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.

Even after the proposal of various solution algorithms, the precise computational complexity of checking whether a Conditional Temporal Network is Dynamically Controllable had still remained widely open. This issue gets settled in this paper which provides constructions, algorithms, and bridging lemmas and arguments to formally prove that: (1) the problem is PSPACE-hard, and (2) the problem lies in PSPACE.

Temporal Functional Dependencies (TFDs for short) are functional dependencies that predicate on temporal databases characterized by a special temporal dimension called valid time (VT). In [1] Combi et al. proposed a uniform framework that subsumes many of the TFDs proposed in literature and, by the combination of them, allow us to express finer constraints. Some interesting constraints are the Temporally Mixed Functional Dependencies (TMFD for short) that allow one to write constraints on the evolution of the data in the database. The problem of checking a TMFD against an instance of a temporal schema is polynomial. We will show that when approximation comes into play (i.e., we look for TMFD holding for almost all database tuples) the problem turns out to be NP-Complete. Moreover we introduce a type of association rules build over TMFD called Temporally Mixed Association Rule (TMAR). We prove that verifying TMAR under approximation is still NP-Complete, by reducing it to a novel problem on directed acyclic graphs.

Conditional Simple Temporal Network (CSTN) is a constraint-based graph-formalism for conditional temporal planning. It offers a more flexible formalism than the equivalent CSTP model of Tsamardinos, Vidal and Pollack, from which it was derived mainly as a sound formalization. Three notions of consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic consistency is the most interesting notion, but it is also the most challenging and it was conjectured to be hard to assess. Tsamardinos, Vidal and Pollack gave a doubly-exponential time algorithm for deciding whether a CSTN is dynamically-consistent and to produce, in the positive case, a dynamic execution strategy of exponential size. In the present work we offer a proof that deciding whether a CSTN is dynamically-consistent is coNP-hard and provide the first singly-exponential time algorithm for this problem, also producing a dynamic execution strategy whenever the input CSTN is dynamically-consistent. The algorithm is based on a novel connection with Mean Payoff Games, a family of two-player infinite games played on finite graphs, well known for having applications in model-checking and formal verification. The presentation of such connection is mediated by the Hyper Temporal Network model, a tractable generalization of Simple Temporal Networks whose consistency checking is equivalent to determining Mean Payoff Games. In order to analyse the algorithm we introduce a refined notion of dynamic-consistency, named ε-dynamic-consistency, and present a sharp lower bounding analysis on the critical value of the reaction time where the CSTN transits from being, to not being, dynamically-consistent. The proof technique introduced in this analysis of the reaction time is applicable more generally when dealing with linear difference constraints which include strict inequalities.

RNA-Seq technology offers new high-throughput ways for transcript identification and quantification based on short reads, and has recently attracted great interest. This is achieved by constructing a weighted DAG whose vertices stand for exons, and whose arcs stand for split alignments of the RNA-Seq reads to the exons. The task consists of finding a number of paths, together with their expression levels, which optimally explain the weights of the graph under various fitting functions, such as least sum of squared residuals. In (Tomescu et al. BMC Bioinformatics, 2013) we studied this genome-guided multi-assembly problem when the number of allowed solution paths was linear in the number of arcs. In this paper, we further refine this problem by asking for a bounded number k of solution paths, which is the setting of most practical interest. We formulate this problem in very broad terms, and show that for many choices of the fitting function it becomes NP-hard. Nevertheless, we identify a natural graph parameter of a DAG G, which we call arc-width and denote ⟨G⟩, and give a dynamic programming algorithm running in time O(W(k)⟨G⟩(k)(⟨G⟩+ k)n) , where n is the number of vertices and W is the maximum weight of G. This implies that the problem is fixed-parameter tractable (FPT) in the parameters W, ⟨G⟩, and k. We also show that the arc-width of DAGs constructed from simulated and real RNA-Seq reads is small in practice. Finally, we study the approximability of this problem, and, in particular, give a fully polynomial-time approximation scheme (FPTAS) for the case when the fitting function penalizes the maximum ratio between the weights of the arcs and their predicted coverage.

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. We introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints. In a Hyper Temporal Network a single temporal constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. As in STNs, a HyTN is consistent when a real value can be assigned to each temporal variable satisfying all the constraints. We show the computational complexity for this generalization and propose effective reduction algorithms for checking consistency of HyTNs unveiling the link with the field of Mean Payoff Games. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, as we show, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs allow to express natural constraints that cannot be expressed by HySTNs like "trigger off an event exactly d min after the occurrence of the last event in a set".

BACKGROUND: Multi-assembly problems have gathered much attention in the last years, as Next-Generation Sequencing technologies have started being applied to mixed settings, such as reads from the transcriptome (RNA-Seq), or from viral quasi-species. One classical model that has resurfaced in many multi-assembly methods (e.g. in Cufflinks, ShoRAH, BRANCH, CLASS) is the Minimum Path Cover (MPC) Problem, which asks for the minimum number of directed paths that cover all the nodes of a directed acyclic graph. The MPC Problem is highly popular because the acyclicity of the graph ensures its polynomial-time solvability. RESULTS: In this paper, we consider two generalizations of it dealing with integrating constraints arising from long reads or paired-end reads; these extensions have also been considered by two recent methods, but not fully solved. More specifically, we study the two problems where also a set of subpaths, or pairs of subpaths, of the graph have to be entirely covered by some path in the MPC. We show that in the case of long reads (subpaths), the generalized problem can be solved in polynomial-time by a reduction to the classical MPC Problem. We also consider the weighted case, and show that it can be solved in polynomial-time by a reduction to a min-cost circulation problem. As a side result, we also improve the time complexity of the classical minimum weight MPC Problem. In the case of paired-end reads (pairs of subpaths), the generalized problem becomes NP-hard, but we show that it is fixed-parameter tractable (FPT) in the total number of constraints. This computational dichotomy between long reads and paired-end reads is also a general insight into multi-assembly problems.

The classical problem of efficiently listing all the simple cycles in a graph has been studied since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most efficient solution was presented by Johnson [SIAM J. Computing, 1975] and takes O((η + 1)(m + n)) time. This solution is not optimal for undirected graphs: nevertheless, no theoretical improvements have been proposed in the past decades. We present the first optimal solution to list all the simple cycles in an undirected graph G. Specifically, let (G) denote the set of all these cycles (| (G)| = η). For a cycle c ∊ (G), let |c| denote the number of edges in c. Our algorithm requires time and is asymptotically optimal: Ω(m) time is necessarily required to read G as input, and time is required to list the output. We also present the first optimal solution to list all the simple paths from s to t (shortly, st-paths) in an undirected graph G. Let st(G) denote the set of st-paths in G and, for an st-path π ∊ st(G), let |π| be the number of edges in π. Our algorithm lists all the st-paths in G optimally in time.

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of minimum and maximum distance constraints between pairs of temporal variables. During construction of an STN, it is possible that the network presents some constraint violations that need to be resolved. One way to solve such violations is to remove a minimal number of constraints, already shown to be an APX-hard problem. Another way is relaxing some constraints in different ways till violations are solved and choosing the best configuration according to one or more criteria. In this paper, assuming that it is possible to increase any constraint bound of an STN paying a constraint-specific cost, we exhibit a polynomial-time algorithm that repairs an STN eliminating all constraint violations at minimum global cost.

BACKGROUND: Through transcription and alternative splicing, a gene can be transcribed into different RNA sequences (isoforms), depending on the individual, on the tissue the cell is in, or in response to some stimuli. Recent RNA-Seq technology allows for new high-throughput ways for isoform identification and quantification based on short reads, and various methods have been put forward for this non-trivial problem. RESULTS: In this paper we propose a novel radically different method based on minimum-cost network flows. This has a two-fold advantage: on the one hand, it translates the problem as an established one in the field of network flows, which can be solved in polynomial time, with different existing solvers; on the other hand, it is general enough to encompass many of the previous proposals under the least sum of squares model. Our method works as follows: in order to find the transcripts which best explain, under a given fitness model, a splicing graph resulting from an RNA-Seq experiment, we find a min-cost flow in an offset flow network, under an equivalent cost model. Under very weak assumptions on the fitness model, the optimal flow can be computed in polynomial time. Parsimoniously splitting the flow back into few path transcripts can be done with any of the heuristics and approximations available from the theory of network flows. In the present implementation, we choose the simple strategy of repeatedly removing the heaviest path. CONCLUSIONS: We proposed a new very general method based on network flows for a multiassembly problem arising from isoform identification and quantification with RNA-Seq. Experimental results on prediction accuracy show that our method is very competitive with popular tools such as Cufflinks and IsoLasso. Our tool, called Traph (Transcrips in gRAPHs), is available at: http://www.cs.helsinki.fi/gsa/traph/.

The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. The xor-genotype data is a cheaply obtainable type of data distinguishing heterozygous from homozygous sites without identifying the homozygous alleles. In this paper, we propose a formulation based on a well-known model used in haplotype inference: pure parsimony. We exhibit exact solutions of the problem by providing polynomial time algorithms for some restricted cases and a fixed-parameter algorithm for the general case. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Furthermore, we show that the problem has a polynomial time k-approximation, where k is the maximum number of xor-genotypes containing a given single nucleotide polymorphisms (SNP). Finally, we propose a heuristic and produce an experimental analysis showing that it scales to real-world large instances taken from the HapMap project.

Abstract Consider the following problem: compute a spanning tree such that the sum of the lengths of its induced fundamental circuits is as small as possible. We motivate why planar square grid graphs are very relevant instances for this problem. In particular, other contributions already showed that the identification of strong lower bounds is highly challenging. Asymptotically, for a graph on n vertices, Alon et al. [SIAM J Comput 24(1995), 78–100] obtained a lower bound of Ω(n log n). We raise the n log n coefficient by a factor of 325. Concerning optimality proofs, the largest grid for which provably optimum solutions were known is 6 × 6, and it was obtained by massive MIP computing power. Here, we present a combinatorial optimality proof even for the 8 × 8 grid. These two results are complemented by new combinatorial lower bounds for the dimensions in which earlier empirical computations were performed, i.e., for up to 10,000 vertices. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

We consider a combinatorial problem derived from haplotyping a population with respect to a genetic disease, either recessive or dominant. Given a set of individuals, partitioned into healthy and diseased, and the corresponding sets of genotypes, we want to infer "bad'' and "good'' haplotypes to account for these genotypes and for the disease. Assume e.g. the disease is recessive. Then, the resolving haplotypes must consist of bad and good haplotypes, so that (i) each genotype belonging to a diseased individual is explained by a pair of bad haplotypes and (ii) each genotype belonging to a healthy individual is explained by a pair of haplotypes of which at least one is good. We prove that the associated decision problem is NP-complete. However, we also prove that there is a simple solution, provided the data satisfy a very weak requirement.

In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push- ased) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.

In this paper, we are interested in the computational complexity of computing (dis)similarity measures between two genomes when they contain duplicated genes or genomic markers, a problem that happens frequently when comparing whole nuclear genomes. Recently, several methods ( [1], [2]) have been proposed that are based on two steps to compute a given (dis)similarity measure M between two genomes G_1 and G_2: first, one establishes a oneto- one correspondence between genes of G_1 and genes of G_2 ; second, once this correspondence is established, it defines explicitly a permutation and it is then possible to quantify their similarity using classical measures defined for permutations, like the number of breakpoints. Hence these methods rely on two elements: a way to establish a one-to-one correspondence between genes of a pair of genomes, and a (dis)similarity measure for permutations. The problem is then, given a (dis)similarity measure for permutations, to compute a correspondence that defines an optimal permutation for this measure. We are interested here in two models to compute a one-to-one correspondence: the exemplar model, where all but one copy are deleted in both genomes for each gene family, and the matching model, that computes a maximal correspondence for each gene family. We show that for these two models, and for three (dis)similarity measures on permutations, namely the number of common intervals, the maximum adjacency disruption (MAD) number and the summed adjacency disruption (SAD) number, the problem of computing an optimal correspondence is NP-complete, and even APXhard for the MAD number and SAD number.

In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push-based) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.

This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a {\rm POPS}(d, g) network either with O({\frac{d}{g}}\log g) deterministic slots, or, with high probability, with 5c\lceil d/g \rceil + o(d/g) + O(\log\log g) randomized slots, where constant c = \exp (1 + e^{-1}) \approx 3.927. When d = \Theta(g), which we claim to be the "interesting” case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2, 2) and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance.

This paper shows that an n=2kprocessor partitioned optical passive stars (POPS) network with g groups and d processors per group can simulate every bidirectional move of an n processor hypercube using one slot when dg. Moreover, the same POPS network can simulate every monodirectional move of a processor hypercube using one slot when d=g. All these results are shown to be optimal. Our simulations improve on the literature whenever dneg and directly yield several important consequences. For example, as a direct consequence of our simulations, a POPS network, n=dg and d2n slots. This is faster than the best previously known ad hoc algorithm and is actually optimal. Similarly, we improve on the best POPS network algorithms for both the prefix sums problem on general POPS networks and the fundamental online permutation routing problem, among others

Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, a data allocation technique is needed to assign data to channels. Partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. The problem of data broadcasting over multiple channels is considered, assuming skewed data allocation to channels and flat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. First, several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels. Specifically, for data items with uniform lengths, an O(NK log N) time algorithm is proposed, which improves over the previously known O(N/sup 2/K) time algorithm. When K/spl les/4, a simpler O(N log N) time algorithm is exhibited which requires only O(N) time if the data items are sorted. Moreover, for data items with nonuniform lengths, it is shown that the problem is NP-hard when K=2 and strong NP-hard for arbitrary K. In the former case, a pseudopolynomial algorithm is discussed whose time is O(NZ), where Z is the sum of the data lengths. In the latter case, an algorithm is devised with time exponential in the maximum data length, which can optimally solve, in reasonable time, only small instances. For larger instances, a new heuristic is devised which is experimentally tested on some benchmarks whose popularities are characterized by Zipf distributions. Such experimental tests reveal that the new heuristic proposed here always outperforms the best previously known heuristic in terms of solution quality.

Summary form only given. Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. In this paper, the problem of data broadcasting over multiple channels is considered assuming skewed data allocation to channels and fiat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. Several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels. Specifically, for data items with uniform lengths, an O(NKlogN) time algorithm is proposed, which improves over the previously known O(N/sup 2/K) time algorithm. When K /spl les/ 4, faster O(N) time algorithms are exhibited. Moreover, for data items with nonuniform lengths, it is shown that the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In the former case, a pseudo-polynomial algorithm is discussed, whose time is O(NZ) where Z is the sum of the data lengths.

In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a 2k− 1-approximation algorithm for the case in which each genotype has at most k ambiguous positions. We further give a new integer-programming formulation that has (for the first time) a polynomial number variables and constraints. Finally, we give approximation algorithms, not based on linear programming, whose running times are almost linear in the input size.

Abstract We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd−1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d‐dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i‐th graph being equal to the size of the item on the i‐th dimension. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 266–280 2004

Abstract We address the problem of finding the largest collection of edge‐disjoint cuts in an undirected graph, dubbed CUT PACKING, focusing on its complexity, about which very little is known. We show a very close relationship with INDEPENDENT SET, namely, for the same graph G , the size of the largest cut packing of G is at least the independence number of G , and at most twice that number. This implies that any approximation guarantee for INDEPENDENT SET immediately extends to CUT PACKING within a factor of 2. In particular, this yields a 2‐approximation algorithm for CUT PACKING in perfect graphs. We then present polynomial‐time algorithms for several classes of perfect (and related) graphs, including triangulated graphs and their complements, bipartite graphs and their complements, and Seymour graphs. Finally, we discuss various linear programming relaxations for the problem, finding combinatorial dual problems of CUT PACKING and characterizing the cases in which duality is strong. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 1–11 2004

This paper gives a new and faster algorithm to find a 1-factor in a bipartite $\Delta$-regular graph. The time complexity of this algorithm is ${\cal O}(n \Delta + n \log n \log \Delta)$, where n is the number of nodes. This implies an ${\cal O}(n \log n \log \Delta + m \log \Delta)$ algorithm to edge-color a bipartite graph with n nodes,m edges, and maximum degree $\Delta$.