Search

Given a connected graph G = (V , E) , with n ≔ | V | vertices and m ≔ | E | edges, a cut can be represented as a bipartition { S , S ¯ } of the vertices or as the set of those edges in E having one endpoint in S and the other in S ¯ , denoted by δ G (S , S ¯). A cut is minimal, or also called bond , if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t , we talk about s , t - bond. In this work, we consider the problems of listing all the bonds and listing all the s , t -bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s , t -bond in O (m) per bond, being thus classified as an O (m) -delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O ˜ (n). By assuming only the two bond-shores are output for every bond, this is the first output-linear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O ˜ (n) + | δ G (S , S ¯) |. • We study the problem of listing all minimal cuts (or bonds) in a graph. • We exploit a different branching strategy than Tsukiyama et al. (1980). • We provide a first algorithm having the same complexity as Tsukiyama et al. (1980). • We rely on dynamic data structures and amortized analysis to improve our approach. • We propose the first O ˜ (n) -delay algorithm to list all bonds in a graph. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Simple Temporal Networks (STNs) are a well-studied model for representing temporal constraints. They comprise a set of time-points (real-valued variables representing execution times) and binary difference constraints among them. Simple Temporal Networks with Uncertainty (STNUs) extend STNs in that some time-points (called contingent) are treated as exogenous variables, whose execution times, bound to fall within a given interval from the corresponding activation time-points (as specified by a "contingent link"), get revealed only during real-time execution. An STNU is dynamically controllable (DC) if there exists a strategy to execute its time-points satisfying all the constraints, regardless of the execution times of contingent time-points 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 any of our 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 previous efficient algorithms for DC-checking. Our analysis also shows: (1) the existence of late execution strategies for STNUs, (2) the equivalence of the notion of DC among several variants of the semantics of STNUs, (3) the existence of a fast algorithm for real-time execution of STNUs, which runs in O (K N) total time in a network with K ≥ 1 contingent links and N ≥ K time points, considerably improving the previous O (N 3) -time bound. [ABSTRACT FROM AUTHOR]

In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w 1 , ... , w n 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. [ABSTRACT FROM AUTHOR]

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et al. (SIAM J Comput 6(3):505-517, 1977). As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e., maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama et al. showed it is O(mn). Makino and Uno (in: Hagerup, Katajainen (eds) Algorithm theory: SWAT 2004. Lecture notes in computer science, Springer, Berlin, pp 260-272, 2004) sharpened the time delay to O(nω) by generating all the children of a node in one single shot, which is performed by computing a square fast matrix multiplication. In this paper we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of n2 nodes in one single shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from O(n2.3728639) to O(n2.093362), keeping a polynomial work space. [ABSTRACT FROM AUTHOR]

The shuffle of two words u and v of A ⁎ is the language u ⧢ v consisting of all words u 1 v 1 u 2 v 2 ... u k v k , where k ≥ 0 and the u i and v i are words of A ⁎ such that u = u 1 u 2 ... u k and v = v 1 v 2 ... v k. In other words, u ⧢ v is the finite set of all words obtainable from merging the words u and v from left to right, but choosing the next symbol arbitrarily from u or v. A word u ∈ A ⁎ is a square for the shuffle product if it is the shuffle of two identical words (i.e. , u ∈ v ⧢ v for some v ∈ A ⁎). Whereas it can be decided in polynomial-time whether or not u ∈ v 1 ⧢ v 2 for given words u , v 1 and v 2 (J.-C. Spehner, 1986 [19]), we show in this paper that it is NP -complete to determine whether or not a word u is a square for the shuffle product. The novelty in our approach lies in representing words as linear graphs , in which deciding whether or not a given word is a square for the shuffle product reduces to computing some inclusion-free perfect matching. Finally, we prove that it is NP -complete to determine whether or not an input word is in the shuffle of a word with its reverse. [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]

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes. [ABSTRACT FROM AUTHOR]

The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif: one where the size of the solution is maximized, the other when the number of substitutions of colors to obtain the motif from the solution is minimized. We also study a decision version of Graph Motif where the connectivity constraint is replaced by the well known notion of graph modularity. While the problem remains N P-complete, it allows algorithms in F P T for biologically relevant parameterizations. [ABSTRACT FROM AUTHOR]

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. [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]

We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes. [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]

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. Algorithmic issues of the C1P are central in computational molecular biology, in particular for physical mapping and ancestral genome reconstruction. In 1972, Tucker gave a characterization of matrices that have the C1P by a set of forbidden submatrices, and a substantial amount of research has been devoted to the problem of efficiently finding such a minimum size forbidden submatrix. This paper presents a new O( Δ m( mΔ+ n)) time algorithm for this particular task for a m× n binary matrix with at most Δ 1-entries per row, thereby improving the O( Δ m( mn+ n)) time algorithm of M. Dom, J. Guo and R. Niedermeier [Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Journal of Computer and System Sciences, 76(3-4): 204-221, ]. Moreover, this approach can be used-with a much heavier machinery-to address harder problems related to Minimal Conflicting Set [G. Blin, R. Rizzi, and S. Vialette. A Polynomial-Time Algorithm for Finding Minimal Conflicting Sets, Proc. 6th International Computer Science Symposium in Russia (CSR), []]. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph , where a nonnegative weight is assigned to each edge of and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless . Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) ), we obtain that the problem is approximable within for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

Clustering, particularly hierarchical clustering, is an important method for understanding and analysing data across a wide variety of knowledge domains with notable utility in systems where the data can be classified in an evolutionary context. This paper introduces a new hierarchical clustering problem defined by a novel objective function we call the arithmeticharmonic cut. We show that the problem of finding such a cut is NP-hard and APX-hard but is fixed-parameter tractable, which indicates that although the problem is unlikely to have a polynomial time algorithm (even for approximation), exact parameterized and local search based techniques may produce workable algorithms. To this end, we implement a memetic algorithm for the problem and demonstrate the effectiveness of the arithmetic-harmonic cut on a number of datasets including a cancer type dataset and a corona virus dataset. We show favorable performance compared to currently used hierarchical clustering techniques such as k-MEANS, Graclus and NORMALIZED-CUT. The arithmetic-harmonic cut metric overcoming difficulties other hierarchal methods have in representing both intercluster differences and intracluster similarities. [ABSTRACT FROM AUTHOR]

Abstract: An excessive factorization of a multigraph is a set of 1-factors of whose union is and, subject to this condition, is minimum. The integer is called the excessive index of and denoted by . We set if an excessive factorization does not exist. Analogously, let be a fixed positive integer. An excessive -factorization is a set of matchings of , all of size , whose union is and, subject to this condition, is minimum. The integer is denoted by and called the excessive -index of . Again, we set if an excessive -factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters and are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive -factorization, respectively, of any bipartite multigraph. [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: We offer the following structural result: every triangle-free graph of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where denotes the odd girth of . In particular, every triangle-free graph of maximum degree 3 has 3 matchings which cover at least of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound. For a fixed value of a parameter , the Maximum -Edge-Colorable Subgraph Problem asks to -edge-color the most of the edges of a simple graph received in input. The problem is known to be -hard for all . However, approximation algorithms with approximation ratios tending to 1 as goes to infinity are also known. At present, the best known performance ratios for the cases and were and , respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case , achieving approximation ratio of . Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of when the input multigraph is restricted to be triangle-free, and of when ’s are also banned). [Copyright &y& Elsevier]

Abstract: Consider a matroid , where denotes the family of bases of , and assign a color to every element (the same color can go to more than one element). The palette of a subset F of E, denoted by , is the image of F under c. Assume also that colors have prices (in the form of a function , where is the label of a color), and define the chromatic price as: . We consider the following problem: find a base such that is minimum. We show that the greedy algorithm delivers a -approximation of the unknown optimal value, where is the rank of matroid . By means of a reduction from SETCOVER, we prove that the ratio cannot be further improved, even in the special case of partition matroids, unless . The results apply to the special case where is a graphic matroid and where the prices are restricted to be all equal. This special case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the ratio achieved by Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function , where F is a common independent set on matroids and, more generally, to independent systems characterized by the k-for-1 property. [Copyright &y& Elsevier]

Abstract: In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle bases. In this paper, we offer an unitary classification accommodating these three classes and further including the following four relevant classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The classification is complete in that, for each ordered pair of classes considered, we either prove that holds for every graph or provide a counterexample graph for which . The seven notions of cycle bases are distinct (either or is exhibited for each pair ). All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the MCB problem naturally associated to each one of these seven classes. Furthermore, we provide a linear time algorithm for computing a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases are of direct use. [Copyright &y& Elsevier]

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 POPS(d, g) network either with O(d/g log g) deterministic slots, or, with high probability, with 5c[d/g] + o(d/g) + O(log log g) randomized slots, where constant c = exp(1 + e-1) ≈ 3.927. When d = ϴ(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. [ABSTRACT FROM AUTHOR]

Abstract: We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min–max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler''s problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose. [Copyright &y& Elsevier]

Abstract: Given a digraph and an , denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an such that is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that is acyclic. (Huang, MacGillivray and Yeo''s result clearly implies an time algorithm to decide but the polynomiality of constructing X was still open.) We define a strongly acyclic digraph as a digraph D such that is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33]. In particular, we avoid decomposing the graph into triconnected components. We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that is acyclic or a proof that D is not acyclically pushable. [Copyright &y& Elsevier]

This paper shows that an n = 2k processor 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 d < g, two slots when d = g, and [d/g] slots when d > g. Moreover, the same POPS network can simulate every monodirectional move of an n processor hypercube using one slot when d = g. All these results are shown to be optimal. Our simulations improve on the literature whenever d ≠ g and directly yield several important consequences. For example, as a direct consequence of our simulations, a POPS network, n = dg and d < g, can compute the prefix sums of n data values in log2 n 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. [ABSTRACT FROM AUTHOR]

It is shown that a Partitioned Optical Passive Stars (POPS) network with g groups and d processors per group can route any permutation among the n=dg processors in one slot when d=1 and 2⌈d/g⌉ slots when d>1. The number of slots used is optimal in the worst case, and is at most the double of the optimum for all permutations π such that π(i)≠i, for all i. [Copyright &y& Elsevier]

We give a simple algorithm for finding a minimum T-cut. At present, all known efficient algorithms for this problem go through the computation of a Gomory–Hu tree. While our algorithm bases on the same fundamental properties of uncrossing as the previous methods, still it provides an ad hoc solution. This solution is easier to implement and faster to run. Our results extend to the whole of symmetric submodular functions. [Copyright &y& Elsevier]

Let G be an undirected graph. The Chinese postman problem (CPP) asks for a shortest postman tour in G, i.e., a closed walk using each edge at least once. The shortest cycle cover problem (SCC) asks for a family C of circuits of G such that each edge is in some circuit of C and the total length of all circuits in C is as small as possible. Clearly, an optimal solution of CPP cannot be greater than a solution of SCC. A graph G has the CPP = SCC property when the solutions to the two problems have the same value. Graph G is said to have the cycle cover property if for every Eulerian 1,2-weighting w : E(G) ↦ {1,2} there exists a family C of circuits of G such that every edge e is in precisely we circuits of C. The cycle cover property implies the CPP = SCC property. We give a counterexample to a conjecture of Zhang (J. Graph Theory 14(5) (1990) 537; Ann. Discrete Math. 55 (1993) 183; Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997; Deans, Graph Structure Theory, AMS, Providence, RI, 1993, pp. 677–688) stating the equivalence of the cycle cover property and the CPP = SCC property for 3-connected graphs. This is also a counterexample to the stronger conjecture of Lai and Zhang, stating that every 3-connected graph with the CPP = SCC property has a nowhere-zero 4-flow. We actually obtain infinitely many cyclically 4-connected counterexamples to both conjectures. [Copyright &y& Elsevier]

We introduce the notion of T-pairing and give a min–max characterization for the minimum size of a T-cut. We show that the coefficients in the minimal TDI system for the T-cut polyhedron can be arbitrarily big. [Copyright &y& Elsevier]

This paper gives a new and faster algorithm to find a 1-factor in a bipartite Δ-regular graph. The time complexity of this algorithm is O(nΔ + n log n log Δ), where n is the number of nodes. This implies an O(n log n log Δ + m log Δ) algorithm to edge-color a bipartite graph with n nodes, in edges, and maximum degree Δ. [ABSTRACT FROM AUTHOR]

The Standard Generalized Markup Language (SGML) and the Extensible Markup Language (XML) allow authors to better transmit the semantics in their documents by explicitly specifying the relevant structures in a document or class of documents by means of document type definitions (DTDs). Several authors have proposed to regard DTDs as extended context-free grammars expressed in a notation similar to extended Backus-Naur form. In addition, the SGML standard allows the semantics of content models (the right-hand side of productions) to be modified by exceptions. Inclusion exceptions allow named elements to appear anywhere within the content of a content model, and exclusion exceptions preclude named elements from appearing in the content of a content model. Since XML does not allow exceptions, the problem of exception removal has received much interest recently. Motivated by this, Kilpeläinen and Wood have proved that exceptions do not increase the expressive power of extended context-free grammars and that for each DTD with exceptions, we can obtain a structurally equivalent extended context-free grammar. Since their argument was based on an exponential simulation, they also conjectured that an exponential blow-up in the size of the grammar is a necessary devil when purging exceptions away. We prove their conjecture under the most realistic assumption that NP-complete problems do not admit non-uniform polynomial-time algorithms. Kilpeläinen and Wood also asked whether the parsing problem for extended context-free grammars with exceptions admits efficient algorithmic solution. We show the NP-completeness of the very basic problem: given a string w and a context-free grammar G (not even extended) with exclusion exceptions (no inclusion exceptions needed), decide whether w belongs to the language generated by G. Our results and arguments point up the limitations of using extended context-free grammars as a model of SGML, especially when one is interested in understanding issues related to exceptions. [ABSTRACT FROM AUTHOR]

Given a directed graph G and a pair of nodes s and t, an s-tbridge of G is an edge whose removal breaks all s-t paths of G (and thus appears in all s-t paths). Computing all s-t bridges of G is 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 walk W is safe with respect to a set W of s-t walks, if W is a subwalk of all walks in W . We start by considering the maximal safe walks when W consists of: all s-t paths, all s-t trails, or all s-t walks of G. We show that the solutions for the first two problems immediately follow from finding all s-t bridges 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 of visible edges. Here we prove a dichotomy between the s-t paths and s-t trails cases, and the s-t walks 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 of s-tarticulation points (nodes appearing in all s-t paths). 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Given an undirected multigraph G = (V , E) with no self-loops, and one of its nodes s ∈ V , we consider the #P-complete problem of counting the number E T s (e) (G) of its Eulerian tours starting and ending at node s. We provide lower and upper bounds on the size of E T s (e) (G) . Namely, let d(v) denote the degree of a node v ∈ V ; we show that max { L 1 (e) , L 2 (e) } ≤ | E T s (e) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! where L 1 (e) = (d (s) - 1) ! ! ∏ v ∈ V \ s (d (v) - 2) ! ! and L 2 (e) = 2 1 - | V | + | E | . We also consider the notion of node-distinct Eulerian tours. Indeed, the classical Eulerian tours are edge-distinct sequences. Node-distinct Eulerian tours, denoted E T s (n) (G) , should instead be different as node sequences. Let Δ (u) be the number of distinct neighbors of a node u, D ⊆ E be the set of distinct edges in the multigraph G, and m(e) for an edge e ∈ E be its multiplicity (i.e. | E | = ∑ e ∈ D m (e) ). We prove that max { L 1 (n) , L 2 (n) , L 3 (n) } ≤ | E T s (n) (G) | ≤ d (s) ∏ v ∈ V (d (v) - 1) ! ! · ∏ e ∈ D m (e) ! - 1 , where L 1 (n) = L 1 (e) / (∏ e ∈ D m (e) !) , L 2 (n) = (Δ (s) - 1) ! ! ∏ v ∈ V \ s (Δ (v) - 2) ! ! , and L 3 (n) = 2 1 - | V | + | D | . We also extend all of our results to graphs having self-loops. [ABSTRACT FROM AUTHOR]

A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of allowed operations is fixed beforehand. Such sequences are useful for instance when reconstructing potential scenarios of evolution between species, or when trying to assess their similarity. We revisit those problems by adding a new constraint on the sequences to be computed: they must avoid a given set of forbidden intermediates , which correspond to species that cannot exist because the mutations that would be involved in their creation are lethal. We initiate this study by focusing on the case where the only mutations that can occur are exchanges of any two elements in the permutations, and give a polynomial time algorithm for solving that problem when the permutation to sort is an involution. [ABSTRACT FROM AUTHOR]

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. [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]

We study a relaxation of the Vector Domination problem called Vector Connectivity ( VecCon ). Given a graph G with a requirement r ( v ) for each vertex v , VecCon asks for a minimum cardinality set S of vertices such that every vertex v ∈ V ∖ S is connected to S via r ( v ) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n -vertex graphs to within a factor of log ⁡ n + 2 , leaving open the question of whether the problem is NP -hard on general graphs. We show that VecCon is APX -hard in general graphs, and NP -hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs. [ABSTRACT FROM AUTHOR]

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]

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 [ABSTRACT FROM AUTHOR]

Abstract: A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting () or crossing (). Given a family of linear graphs, and a non-empty subset , we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge pairs all comparable by one of the relations in , that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for -structured patterns and -structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) for -structured patterns, (ii) for -structured patterns, and (iii) for -structured patterns, where is the size of the optimal solution and is the th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding. [Copyright &y& Elsevier]

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 to model temporal plans with decisions. 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. In this paper, we deal with the use of STNDs for modeling and synthesizing execution strategies. We propose an incremental hybrid SAT-based consistency checking algorithm for STNDs that is faster than the one previously proposed and allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). We carry out an experimental evaluation with Kappa, a tool that we developed for STNDs. We also show that any STND can be easily translated into a disjunctive temporal network and vice versa. [ABSTRACT FROM AUTHOR]

Abstract: Given a (possibly infinite) family of oriented stars, an -packing in a digraph D is a collection of vertex disjoint subgraphs of D, each isomorphic to a member of . The -Packing problem asks for the maximum number of vertices, of a host digraph D, that can be covered by an -packing of D. We prove a dichotomy for the decision version of the -packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problems, we provide Hall type min-max theorems, including versions for (locally) degree-constrained variants of the problems. An oriented star can be specified by a pair of denoting the number of out- and in-neighbours of the centre vertex. For , we denote by the family of stars such that , and , and . We prove the -Packing problem is polynomial if for some , and NP-complete otherwise. [Copyright &y& Elsevier]

Given a string s on an alphabet Σ, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem are polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases. [ABSTRACT FROM AUTHOR]

A ‘simulation program with integrated circuit emphasis’ (SPICE) model for the evaluation, in frequency and time domain, of the coupling of a bundle of shielded coaxial cables with an external electromagnetic source such as a bulk current injection clamp, is developed. The proposed equivalent circuit takes into account the presence of the transfer impedance and the presence of the transfer admittance, and it does not need the subdivision in elementary cells. Intermediate results are validated by comparing the exact numerical solutions with the output of the SPICE circuit, and the final results are validated by means of comparison with measurements carried out on an experimental setup. The feature selective validation (FSV) technique is used as a measure of the comparisons. [ABSTRACT FROM AUTHOR]