Search

Consider the following natural variation of the degree realization problem. Let G = (V , E) be a simple undirected graph of order n. Let f ∈ R ≥ 0 n be a vector of vertex requirements , and let w ∈ R ≥ 0 n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑ j ∈ N (i) w j = f i are satisfied for all i ∈ V , where N (i) denotes the neighbourhood of vector i. Given a requirements vector f , the Vertex-Weighted Graph Realization problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In this paper, we consider two avenues. We initiate a study that focuses on weighted realizations where the graph is required to be of a specific class by providing a full characterization of realizable requirement vectors for paths and acyclic graphs. However, checking the respective criteria is shown to be NP-hard. In the second part, we advance the study in general graphs which was started in [2]. For the unsolved cases, the question of whether a vector f is realizable can be formulated as whether its largest requirement lies within certain intervals. We describe several new, realizable intervals and show the existence of an interval that cannot be realized. The complete classification for general graphs is an open problem. [ABSTRACT FROM AUTHOR]

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamčik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Δ is acyclically edge (Δ + 2) -colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph. • Consider a long-standing open conjecture on graph acyclic edge coloring. • Show that for planar graphs without intersecting triangles, the conjecture holds true. • Adapt discharging methods to reduce local structures to only six specified groups. • Design re-coloring techniques for each group and prove the conjecture by induction on the edge number. [ABSTRACT FROM AUTHOR]

We propose a dynamic programming framework for an exact multi-stage (lexicographic) combinatorial optimization. Unlike conventional algorithms of dynamic programming that return one optimal solution, two dynamic programming algorithms proposed in this paper are coping with the whole set of optimal solutions or with its essential part. We describe the set of elements for optimization by a labeled directed acyclic graph, which in some sense, is similar to the structure of subproblems of the considered problem. For a given cost function (objective), the first algorithm constructs a subgraph of this graph that describes the whole set of optimal elements or its essential part. This algorithm can be used for multi-stage optimization of elements relative to a sequence of cost functions. The second algorithm counts elements before the optimization and after each optimization step. The considered labeled directed acyclic graph is a kind of circuit. This circuit builds the set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets attached to unifying nodes and functional operations attached to functional nodes. The algorithms for optimization and counting elements are defined for an arbitrary circuit without repetitions in which each element is generated exactly one time. For a considered problem with a known conventional dynamic programming solution algorithm, usually, it is easy to construct a corresponding circuit without repetitions. Once the circuit and cost functions are defined, our framework provides the correctness proofs and detailed time complexity analysis for the proposed algorithms. To make this approach more intuitive, we consider an illustrative example related to the maximum subarray problem. We tested our approach on the following nine combinatorial optimization problems: matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, optimal bitonic tour, segmented least squares, convex polygon triangulation, one-dimensional clustering, and line breaking (text justification). We consider the last three problems in detail: construct a circuit without repetitions, describe at least two cost functions, evaluate a number of operations and time required by the algorithms, discuss an example, and consider the results of computer experiments with randomly generated instances of the problem. [ABSTRACT FROM AUTHOR]

Abstract The rise of repetitive datasets has lately generated a lot of interest in compressed self-indexes based on dictionary compression, a rich and heterogeneous family of techniques that exploits text repetitions in different ways. For each such compression scheme, several different indexing solutions have been proposed in the last two decades. To date, the fastest indexes for repetitive texts are based on the run-length compressed Burrows–Wheeler transform (BWT) and on the Compact Directed Acyclic Word Graph (CDAWG). The most space-efficient indexes, on the other hand, are based on the Lempel–Ziv parsing and on grammar compression. Indexes for more universal schemes such as collage systems and macro schemes have not yet been proposed. Very recently, Kempa and Prezza [STOC 2018] showed that all dictionary compressors can be interpreted as approximation algorithms for the smallest string attractor , that is, a set of text positions capturing all distinct substrings. Starting from this observation, in this paper we develop the first universal compressed self-index, that is, the first indexing data structure based on string attractors, which can therefore be built on top of any dictionary-compressed text representation. Let γ be the size of a string attractor for a text of length n. From known reductions, γ can be chosen to be asymptotically equal to any repetitiveness measure: number of runs in the BWT, size of the CDAWG, number of Lempel–Ziv phrases, number of rules in a grammar or collage system, size of a macro scheme. Our index takes O (γ lg ⁡ (n / γ)) words of space and supports locating the occ occurrences of any pattern of length m in O (m lg ⁡ n + o c c lg ϵ ⁡ n) time, for any constant ϵ > 0. This is, in particular, the first index for general macro schemes and collage systems. Our result shows that the relation between indexing and compression is much deeper than what was previously thought: the simple property standing at the core of all dictionary compressors is sufficient to support fast indexed queries. [ABSTRACT FROM AUTHOR]

Abstract The Weak Dominance Drawing problem can be defined as follows: given a directed acyclic graph G , find two topological sorts, t X and t Y , minimizing the size of the intersection between them. The intersection of two topological sorts is defined as the set of ordered pair of vertices (u , v) such that t X (u) < t X (v) and t Y (u) < t Y (v). In this work we consider a variation of this problem, that we call One-Sided Weak Dominance Drawing , in which one of the topological sorts is given as input and we must find another topological sort minimizing the intersection set with the given one. This problem has been considered in the literature and its applications include index generation of competitive algorithms for reachability queries on very large graphs. In this paper we formalize the problem, describe one of its applications, show how the problem is currently tackled in the literature, prove that its decision version is NP-complete and determine a primal bound for it as a function of the dimension of G. [ABSTRACT FROM AUTHOR]

Abstract: Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in worst-case time, which allowed it to be integrated as part of an time all-pairs algorithm. Here and respectively denote the number of edges and vertices in the graph, while denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just time. This can be integrated as part of the time spent solving single-source, improving on the value of obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in time and included as part of the time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from to . [Copyright &y& Elsevier]

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble . In this paper, we propose an O ( n + m ) -time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O ( m log ⁡ m ) -time algorithm by Sung et al. [ABSTRACT FROM AUTHOR]

Abstract: In programming languages with dynamic use of memory, such as Java, knowing that a reference variable x points to an acyclic data structure is valuable for the analysis of termination and resource usage (e.g., execution time or memory consumption). For instance, this information guarantees that the depth of the data structure to which x points is greater than the depth of the data structure pointed to by x. for any field of x. This, in turn, allows bounding the number of iterations of a loop which traverses the structure by its depth, which is essential in order to prove the termination or infer the resource usage of the loop. The present paper provides an Abstract-Interpretation-based formalization of a static analysis for inferring acyclicity, which works on the reduced product of two abstract domains: reachability, which models the property that the location pointed to by a variable can be reached by dereferencing another variable (in this case, is said to reach ); and cyclicity, modeling the property that can point to a cyclic data structure. The analysis is proven to be sound and optimal with respect to the chosen abstraction. [Copyright &y& Elsevier]

Abstract: In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series–parallel graphs or generalized series–parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time. [ABSTRACT FROM AUTHOR]