Complexities of some interesting problems on spanning trees

This paper deals with the complexity issues of some new interesting spanning tree problems. Here we define some new spanning tree problems by imposing various constraints and restrictions on graph parameters and present relevant results. Also we introduce a new notion of “set version” of some decision problems having integer K<|V| as a parameter in the input instance, where we replace K by a set X⊆|V|. For example, the set version of Maximum Leaf Spanning Tree problem asks whether there exists a spanning tree in G that contains X as a subset of the leaf set. We raise the issue of whether the set versions of NP-complete problems are as hard as the original problems and prove that although in some cases the set versions are easier to solve, this is not necessarily true in general.     

Variations of the maximum leaf spanning tree problem for bipartite graphs

The maximum leaf spanning tree problem is known to be NP-complete. In [M.S. Rahman, M. Kaykobad, Complexities of some interesting problems on spanning trees, Inform. Process. Lett. 94 (2005) 93-97], a variation on this problem was posed. This variation restricts the problem to bipartite graphs and asks, for a fixed integer K, whether or not the graph contains a spanning tree with at least K leaves in one of the partite sets. We show not only that this problem is NP-complete, but that it remains NP-complete for planar bipartite graphs of maximum degree 4. We also consider a generalization of a related decision problem, which is known to be polynomial-time solvable. We show the problem is still polynomial-time solvable when generalized to weighted graphs.     

Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets

Phylogenetic networks are a generalization of phylogenetic trees that are used in biology to represent reticulate or non-treelike evolution. Recently, several algorithms have been developed which aim to construct phylogenetic networks from biological data using triplets, i.e. binary phylogenetic trees on 3-element subsets of a given set of species. However, a fundamental problem with this approach is that the triplets displayed by a phylogenetic network do not necessarily uniquely determine or encode the network. Here we propose an alternative approach to encoding and constructing phylogenetic networks, which uses phylogenetic networks on 3-element subsets of a set, or trinets, rather than triplets. More specifically, we show that for a special, well-studied type of phylogenetic network called a 1-nested network, the trinets displayed by a 1-nested network always encode the network. We also present an efficient algorithm for deciding whether a dense set of trinets (i.e. one that contains a trinet on every 3-element subset of a set) can be displayed by a 1-nested network or not and, if so, constructs that network. In addition, we discuss some potential new directions that this new approach opens up for constructing and comparing phylogenetic networks.     

无线移动网络分布式最小生成树的声明实现

声明网络是一种应用演绎数据库技术描述并解决网络问题的方法.节点将网络封装为数据库的一部分,通过对数据库的操作解决网络问题.最小生成树问题是无线Ad Hoc网络上NP完全问题,声明网络为无线Ad Hoc网络的最小生成树问题提供了一种新的解决方案.声明最小生成树协议可以分布式地构建无线Ad Hoc网络的最小生成树,在仿真平台的实验结果表明,声明最小生成树协议达到了收敛速度快的要求.     

Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems

We present a framework for an automated generation of exact search tree algorithms for NP-hard problems. The purpose of our approach is twofold—rapid development and improved upper bounds. Many search tree algorithms for various problems in the literature are based on complicated case distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms. Moreover, using the sheer computing power of machines it may also lead to improved upper bounds on search tree sizes (i.e., faster exact solving algorithms) in comparison with previously developed hand-made search trees. Among others, such an example is given with the NP-complete Cluster Editing problem (also known as Correlation Clustering on complete unweighted graphs), which asks for the minimum number of edge additions and deletions to create a graph which is a disjoint union of cliques. The hand-made search tree for Cluster Editing had worst-case size O(2.27^k), which now is improved to O(1.92^k) due to our new method. (Herein, k denotes the number of edge modifications allowed.)     

Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation

We present efficient fixed-parameter algorithms for the NP-complete edge modification problems Cluster Editing and Cluster Deletion. Here, the goal is to make the fewest changes to the edge set of an input graph such that the new graph is a vertex-disjoint union of cliques. Allowing up to k edge additions and deletions (Cluster Editing), we solve this problem in O(2.27^k + |V|³) time; allowing only up to k edge deletions (Cluster Deletion), we solve this problem in O(1.77^k + |V|³) time. The key ingredients of our algorithms are two easy to implement bounded search tree algorithms and an efficient polynomial-time reduction to a problem kernel of size O(k³). This improves and complements previous work. Finally, we discuss further improvements on search tree sizes using computer-generated case distinctions.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.     

Multi-objective evolutionary algorithms and phylogenetic inference with multiple data sets

Evolutionary relationships among species are usually (1) illustrated by means of a phylogenetic tree and (2) inferred by optimising some measure of fitness, such as the total evolutionary distance between species or the likelihood of the tree (given a model of the evolutionary process and a data set). The combinatorial complexity of inferring the topology of the best tree makes phylogenetic inference an ideal candidate for evolutionary algorithms. However, difficulties arise when different data sets provide conflicting information about the inferred `best' tree(s). We apply the techniques of multi-objective optimisation to phylogenetic inference for the first time. We use the simplest model of evolution and a four species problem to illustrate the method.     

Locating centers in a dynamically changing network,and related problems

In a dynamically changing network, the costs or distances between locations are changing in each discrete time period. We consider the location of emergency facilities that must minimize the maximum distance to any customer on the network across all time periods. We call the problem of locating p centers over k underlying networks corresponding to k periods the k-Network p-Center problem. The problem is considered when, in each period, the network satisfies the triangle inequality. In this paper, we provide a polynomial time 3-approximation algorithm for Δ k-Network p-Center for the case k=2. We discuss generalizations inspired by this problem to other optimization problems with multiple underlying networks and the objective of finding a single solution that varies as little as possible from the optimum for each network. The additional combinatorial problems discussed include: sorting; perfect matching; shortest path; minimum spanning tree; and minimum cut. All are shown to be NP-hard for k⩾2.     

Clustering based distributed phylogenetic tree construction

Phylogenetic tree construction has received much attention recently due to the availability of vast biological data. In this study, we provide a three step method to build phylogenetic trees. Firstly, a density-based clustering algorithm is used to provide clusters of the population at hand using the distance matrix which shows the distances of the species. Secondly, a phylogenetic tree for each cluster is constructed by using the neighbor-joining (NJ) algorithm and finally, the roots of the small phylogenetic trees are connected again by the NJ algorithm to form one large phylogenetic tree. To our knowledge, this is the first method for building phylogenetic trees that uses clustering prior to forming the tree. As such, it provides independent phylogenetic tree formation within each cluster as the second step, hence is suitable for parallel/distributed processing, enabling fast processing of very large biological data sets.The proposed method, clustered neighbor-joining (CNJ) is applied to 145 samples from the Y-DNA Haplogroup G. Distances between male samples are the variation in their set of Y-chromosomal short tandem repeat (STR) values. We show that the clustering method we use is superior to other clustering methods as applied to Y-DNA data and also independent, fast distributed construction of phylogenetic trees is possible with this method.     

A fixed-parameter algorithm for minimum quartet inconsistency

Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the Minimum Quartet Inconsistency (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet topologies. The more general problem where we are not necessarily given a topology for every subset of four taxa appears to be fixed-parameter intractable. For MQI, however, which is also NP-complete, we can compute the required tree in time O(4^kn+n⁴). This means that the problem is fixed-parameter tractable and that in the case of a small number k of “errors” the tree reconstruction can be done efficiently. In particular, for minimal k, our algorithm can produce all solutions that resolve k errors. Additionally, we discuss significant heuristic improvements. Experiments underline the practical relevance of our solutions.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.     

Strong NP-completeness of a matrix similarity problem

Consider the following problem: given an upper triangular matrix A, with rational entries and distinct diagonal elements, and a tolerance τ ⩾ 1, decide whether there exists a nonsingular matrix G, with condition number bounded by τ, such that G⁻¹AG is 2 × 2 block diagonal. This problem, which we shall refer to as DICHOTOMY, is an important one in the theory of invariant subspaces. It has recently been proved that DICHOTOMY is NP-complete. In this note we make some progress proving that DICHOTOMY is actually NP-complete in the strong sense. This outlines the “purely combinatorial” nature of the difficulty, which might well arise even in case of well scaled matrices with entries of small magnitude.     

Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the cost constrained minimum label spanning tree (CCMLST) problem is to find a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. The label constrained minimum spanning tree (LCMST) problem is closely related to the CCMLST problem. Here, we are given a threshold K on the number of labels. The goal is to find a minimum weight spanning tree that uses at most K distinct labels. Both of these problems are motivated from the design of telecommunication networks and are known to be NP-complete [15].In this paper, we present a variable neighborhood search (VNS) algorithm for the CCMLST problem. The VNS algorithm uses neighborhoods defined on the labels. We also adapt the VNS algorithm to the LCMST problem. We then test the VNS algorithm on existing data sets as well as a large-scale dataset based on TSPLIB [12] instances ranging in size from 500 to 1000 nodes. For the LCMST problem, we compare the VNS procedure to a genetic algorithm (GA) and two local search procedures suggested in [15]. For the CCMLST problem, the procedures suggested in [15] can be applied by means of a binary search procedure. Consequently, we compared our VNS algorithm to the GA and two local search procedures suggested in [15]. The overall results demonstrate that the proposed VNS algorithm is of high quality and computes solutions rapidly. On our test datasets, it obtains the optimal solution in all instances for which the optimal solution is known. Further, it significantly outperforms the GA and two local search procedures described in [15].     

Closure properties and decision problems of dag automata

Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.     

Optimizing server placement in distributed systems in the presence of competition

Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server.Our major results include three parts. First, for tree-structured systems, we propose an O(|V|³k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with |V| nodes. We also propose an O(|V|³) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, called Greedy Add, Greedy Remove and Greedy Add-Remove, to solve them. Third, we show that if the number of requests a server can handle (i.e., server capacity) is bounded, the server placement problem is NP-complete even for tree networks. We then derive a variation of the same set of greedy heuristic algorithms, with consideration of server capacity constraint, to solve the problem.Our experiment results demonstrate that the greedy algorithms achieve good results, when compared with the upper bounds found by a linear programming algorithm. Greedy Add performs best in the unconstrained model, yielding a benefit within 12% difference from the theoretical upper bound in average. For the constrained model, Greedy Remove performs best for smaller network sizes, while Greedy Add-Remove performs best for larger network sizes. On average, the heuristic algorithms yield a benefit within 13% difference from the theoretical upper bound in the constrained model.     

The transposition median problem is NP-complete

During recent years, the genomes of more and more species have been sequenced, providing data for phylogenetic reconstruction based on genome rearrangement measures, where the most important distance measures are the reversal distance and the transposition distance. The two main tasks in all phylogenetic reconstruction algorithms are to calculate pairwise distances and to solve the median of three problem. While the reversal distance problem can be solved in linear time, the reversal median problem has been proven to be NP-complete. The status of the transposition distance problem is still open, but it is conjectured to be more difficult than the reversal problem. This, in turn, also suggests that the transposition median problem is NP-complete. However, this conjecture could not yet be proven. We have now succeeded in giving a non-trivial proof for the NP-completeness of the transposition median problem.     

On a class of branching problems in broadcasting and distribution

We introduce the following network optimization problem: given a directed graph with a cost function on the arcs, demands at the nodes, and a single source s, find the minimum cost connected subgraph from s such that its total demand is no less than lower bound D. We describe applications of this problem to disaster relief and media broadcasting, and show that it generalizes several well-known models including the knapsack problem, the partially ordered knapsack problem, the minimum branching problem, and certain scheduling problems. We prove that our problem is strongly NP-complete and give an integer programming formulation. We also provide five heuristic approaches, illustrate them with a numerical example, and provide a computational study on both small and large sized, randomly generated problems. The heuristics run efficiently on the tested problems and provide solutions that, on average, are fairly close to optimal.     

Single machine weighted earliness–tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness–tardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete. While dynamic programming formulation runs out of memory for large problem instances, depth-first branch-and-bound formulation runs slow for large problems since it uses a tree search space. In this paper, we have suggested an algorithm to optimally solve large instances of the restricted version of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when available memory is limited. It has been found to run faster than dynamic programming and depth-first branch-and-bound formulations and can solve much larger instances of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail.Scope and purposeA class of single machine problems arising out of scheduling jobs in JIT environment has been considered in this paper. The objective is to minimize the total weighted earliness–tardiness penalties of jobs. In this paper, we have presented a new algorithm and conducted extensive empirical runs to show that the new algorithm performs much better than the existing approaches in solving large instances of the problem.