Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing possibly discordant evolutionary scenarios ...
详细信息
ISBN:
(数字)9783319674285
ISBN:
(纸本)9783319674285;9783319674278
Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing possibly discordant evolutionary scenarios for a given set of genes or species, and aims at finding a single tree that minimizes the leaf-removal distance to the input trees. This problem is a specific instance of the general consensus/super-tree problem, widely used to combine or summarize discordant evolutionary trees. The problem we introduce is specifically tailored to address the case of discrepancies between the input trees due to the misplacement of individual taxa. Most supertree or consensus tree problems are computationally intractable, and we show that the problem we introduce is also NP-hard. We provide tractability results in form of a 2-approximation algorithm and a parameterized algorithm with respect to the number of removed leaves. We also introduce a variant that minimizes the maximum number d of leaves that are removed from any input tree, and provide a parameterized algorithm for this problem with parameter d.
We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most 6k + 5 under the promise that the treewidth of G never grow...
详细信息
ISBN:
(纸本)9798350318944
We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most 6k + 5 under the promise that the treewidth of G never grows above k. The amortized update time is O-k(2(root log n log log n)), where n is the vertex count of G and the O-k(.) notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle's Theorem: for any fixed property phi expressible in the CMSO2 logic, the data structure can maintain whether G satisfies phi within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].
We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G(1), G(2), either concludes that one of these graphs has treewidth at least k, or determines whether G(1) and G(2) are isomorphic...
详细信息
ISBN:
(纸本)9781479965175
We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G(1), G(2), either concludes that one of these graphs has treewidth at least k, or determines whether G(1) and G(2) are isomorphic. The running time of the algorithm on an n-vertex graph is 2(O(k5 log k)) . n(5), and this is the first fixed-parameter algorithm for GRAPH ISOMORPHISM parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2(O(k5 log k)) . n(5) time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k(4)). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G(1) and G(2) are equal.
Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns...
详细信息
In many settings there is a need to reduce the spread of something undesirable, such as a virus, through a network. Typically, the network in which the spreading process takes place is not fixed but is subject to disc...
详细信息
ISBN:
(数字)9783031087400
ISBN:
(纸本)9783031087400;9783031087394
In many settings there is a need to reduce the spread of something undesirable, such as a virus, through a network. Typically, the network in which the spreading process takes place is not fixed but is subject to discrete changes over time;a natural formalism for such networks is that of temporal graphs. In this paper we survey three types of modifications that have been proposed in order to reduce reachability in temporal graphs, as well as the computational complexity of identifying optimal strategies for reducing reachability using each type of modification. We then go on to discuss several limitations of the current frameworks as models for intervention against real-world spreading processes, and suggest how these might be addressed in future research.
Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In ...
详细信息
Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for MINIMUM MAXIMAL MATCHING and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.
Graph editing problems have a long history and have been widely studied, with applications in biochemistry and complex network analysis. They generally ask whether an input graph can be modified by inserting and delet...
详细信息
Graph editing problems have a long history and have been widely studied, with applications in biochemistry and complex network analysis. They generally ask whether an input graph can be modified by inserting and deleting vertices and edges to a graph with the desired property. We consider the problem \textsc{Graph-Edit-to-NDL} (GEN) where the goal is to modify to a graph with a given neighbourhood degree list (NDL). The NDL lists the degrees of the neighbours of vertices in a graph, and is a stronger invariant than the degree sequence, which lists the degrees of vertices. We show \textsc{Graph-Edit-to-NDL} is NP-complete and study its parameterized complexity. In parameterized complexity, a problem is said to be fixed-parameter tractable with respect to a parameter if it has a solution whose running time is a function that is polynomial in the input size but possibly superpolynomial in the parameter. Golovach and Mertzios [ICSSR, 2016] studied editing to a graph with a given degree sequence and showed the problem is fixed-parameter tractable when parameterized by $\Delta+\ell$, where $\Delta$ is the maximum degree of the input graph and $\ell$ is the number of edits. We prove \textsc{Graph-Edit-to-NDL} is fixed-parameter tractable when parameterized by $\Delta+\ell$. Furthermore, we consider a harder problem \textsc{Constrained-Graph-Edit-to-NDL} (CGEN) that imposes constraints on the NDLs of intermediate graphs produced in the sequence. We adapt our FPT algorithm for \textsc{Graph-Edit-to-NDL} to solve \textsc{Constrained-Graph-Edit-to-NDL}, which proves \textsc{Constrained-Graph-Edit-to-NDL} is also fixed-parameter tractable when parameterized by $\Delta+\ell$. Our results imply that, for graph properties that can be expressed as properties of NDLs, editing to a graph with such a property is fixed-parameter tractable when parameterized by $\Delta+\ell$. We show that this family of graph properties includes some well-known graph measures used in complex network ana
The k-path problem is to find a simple path of length k. Thisproblem is NP-complete and has applications in bioinformatics fordetecting signaling pathways in protein interaction networks and for biological subnetwork ...
详细信息
The k-path problem is to find a simple path of length k. This
problem is NP-complete and has applications in bioinformatics for
detecting signaling pathways in protein interaction networks and for biological subnetwork matching. There are algorithms implemented to
solve the problem for k up to 13. The fastest implementation has
running time O^*(4.32^k), which is slower than the best known algorithm of running time O^*(4^k). To implement the best known algorithm for the k-path problem, we need to construct (n,k)-universal set.
In this thesis, we study the practical algorithms for constructing the (n,k)-universal set problem. We propose six algorithm variants to
handle the increasing computational time and memory space needed for
k=3, 4, ..., 8. We propose two major empirical techniques that cut
the time and space tremendously, yet generate good results. For the case k=7, the size of the universal set found by our algorithm is 1576, and is 4611 for the case k=8.
We implement the proposed algorithms with the OpenMP parallel interface and construct universal sets for k=3, 4, ..., 8. Our experiments show that our algorithms for the (n,k)-universal set problem exhibit very good parallelism and hence shed light on its MPI implementation.
Ours is the first implementation effort for the (n,k)-universal set
problem. We share the effort by proposing an extensible universal set construction and retrieval system. This system integrates universal set construction algorithms and the universal sets constructed. The sets are
stored in a centralized database and an interface is provided to access the database easily.
The (n,k)-universal set have been applied to many other NP-complete
problems such as the set splitting problems and the matching
and packing problems. The small (n,k)-universal set constructed
by us will reduce significantly the time to solve those problems.
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Departme...
详细信息
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, parameterized algorithms, Approxi- mation algorithms, Bidirected Graphs iii
暂无评论