A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks

Genetic algorithms and other evolutionary algorithms have been successfully applied to solve constrained minimum spanning tree problems in a variety of communication network design problems. In this paper, we enlarge the application of these types of algorithms by presenting a multi-population hybrid genetic algorithm to another communication design problem. This new problem is modeled through a hop-constrained minimum spanning tree also exhibiting the characteristic of flows. All nodes, except for the root node, have a nonnegative flow requirement. In addition to the fixed charge costs, nonlinear flow dependent costs are also considered. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem and we have termed it hop-constrained minimum cost flow spanning tree problem. The efficiency and effectiveness of the proposed method can be seen from the computational results reported.     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

The complete optimal stars-clustering-tree problem

We consider the following complete optimal stars-clustering-tree problem: Given a complete graph G=(V,E) with a weight on every edge and a collection of subsets of V, we want to find a minimum weight spanning tree T such that each subset of the vertices in the collection induces a complete star in T. One motivation for this problem is to construct a minimum cost (weight) communication tree network for a collection of (not necessarily disjoint) groups of customers such that each group induces a complete star. As a result the network will provide a “group broadcast” property, “group fault tolerance” and “group privacy”. We present another motivation from database systems with replications. For the case where the intersection graph of the subsets is connected we present a structure theorem that describes all feasible solutions. Based on it we provide a polynomial algorithm for finding an optimal solution. For the case where each subset induces a complete star minus at most k leaves we prove that the problem is NP-hard.     

Approximating k-hop minimum-spanning trees

Given a complete graph on~n nodes with metric edge costs, the minimum-costk-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in the tree has at most k edges. We present an algorithm that computes such a tree of total expected cost times that of a minimum-cost k-hop spanning-tree.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Approximations for two variants of the Steiner tree problem in the Euclidean plane {\mathbb{R}^2}

Given n terminals in the Euclidean plane and a positive constant l, find a Steiner tree T interconnecting all terminals with the minimum total cost of Steiner points and a specific material used to construct all edges in T such that the Euclidean length of each edge in T is no more than l. In this paper, according to the cost b of each Steiner point and the different costs of some specific materials with the different lengths, we study two variants of the Steiner tree problem in the Euclidean plane as follows: (1) If a specific material to construct all edges in such a Steiner tree has its infinite length and the cost of per unit length of such a specific material used is c ₁, the objective is to minimize the total cost of the Steiner points and such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_1+ c_1 \cdot \sum_{e \in T} w(e)\}}$ , where T is a Steiner tree constructed, k ₁ is the number of Steiner points and w(e) is the length of part cut from such a specific material to construct edge e in T, and we call this version as the minimum-cost Steiner points and edges problem (MCSPE, for short). (2) If a specific material to construct all edges in such a Steiner tree has its finite length L (l ≤ L) and the cost of per piece of such a specific material used is c ₂, the objective is to minimize the total cost of the Steiner points and the pieces of such a specific material used to construct all edges in T, i.e., ${{\rm min} \{b \cdot k_2+ c_2 \cdot k_3\}}$ , where T is a Steiner tree constructed, k ₂ is the number of Steiner points in T and k ₃ is the number of pieces of such a specific material used, and we call this version as the minimum-cost Steiner points and pieces of specific material problem (MCSPPSM, for short). These two variants of the Steiner tree problem are NP-hard with some applications in VLSI design, WDM optical networks and wireless communications. In this paper, we first design an approximation algorithm with performance ratio 3 for the MCSPE problem, and then present two approximation algorithms with performance ratios 4 and 3.236 for the MCSPPSM problem, respectively.     

On the complexity of a family of generalized matching problems

We consider a family of generalized matching problems called k-feasible matching (k-RM) problems, where k? {1,2,3,…} ∪ {∞}. We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of {1,2,…} ∪ {∞}, there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

New branch-and-bound algorithms for k-cardinality tree problems

Given an undirected graph, the k-cardinality tree problem (KCTP) is the problem of finding a subtree with exactly k edges whose sum of weights is minimum. In this paper we present a lower bound for KCTP based on the work by Kataoka et al. [Kataoka, S., N. Araki and T. Yamada, Upper and lower bounding procedures for the minimum rooted k-subtree problem, European Journal of Operational Research, 122 (2000), 561–569]. This new bound is the basis for the development of a branch-and-bound algorithm for the problem. Experiments carried out on instances from KCTLib revealed that the new exact algorithm largely outperforms the previous approach.     

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree in a network where nodes have specified demands, with an additional capacity constraints on the subtrees incident to a given source node s. The capacitated minimum spanning tree problem arises as an important subproblem in many telecommunication network design problems. In a recent paper, Ahuja et al. (Math. Program. 91 (2001) 71) proposed two very large-scale neighborhood search algorithms for the capacitated minimum spanning tree problem. Their first node-based neighborhood structure is obtained by performing multi-exchanges involving several trees where each tree contributes a single node. Their second tree-based neighborhood structure is obtained by performing multi-exchanges where each tree contributes a subtree. The computational investigations found that node-based multi-exchange neighborhood gives the best performance for the homogenous demand case (when all nodes have the same demand), and the tree-based multi-exchange neighborhood gives the best performance for the heterogeneous demand case (when nodes may have different demands). In this paper, we propose a composite neighborhood structure that subsumes both the node-based and tree-based neighborhoods, and outperforms both the previous neighborhood search algorithms for solving the capacitated minimum spanning tree problem on standard benchmark instances. We also develop improved dynamic programming based exact algorithms for searching the composite neighborhood.     

The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

The geometric generalized minimum spanning tree problem with grid clustering

This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly -hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering.     

Mixed convexity and optimization results for an (S ? 1, S) inventory model under a time limit on backorders

Das (Oper Res 25(5):835–850, 1977) considered the optimization of a cost function associated with an (S ? 1, S) inventory model assuming the parameters to be the initial number of items in the stock and the service rate. A similar optimization problem associated with an M/E _k /1 queueing system with parameters being the number of servers and the service rate was considered by Kumin (Manag Sci 20:126–129, 1973). Both carried out case-dependent computations and indicated the difficulty of finding general convexity and optimization results for functions with both integer and real variables. In this paper, generalized mixed convexity and computational optimization results for the cost function associated with the (S ? 1, S) inventory system suggested by Das are provided. The generalized convexity results determine the convexity region of the cost function, and therefore the region of possible minimal values of the cost function in the domain. In addition, algorithms to determine the generalized convexity and computational optimization results for the cost function are given.     

Mutual exclusion scheduling with interval graphs or related classes, Part I

In this paper, the mutual exclusion scheduling problem is addressed. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93-109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the NP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.     

The d-precoloring problem for k-degenerate graphs

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

A tight bound on the min-ratio edge-partitioning problem of a tree

In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k≤n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

Solving covering problems and the uncapacitated plant location problem on trees

Given a tree network on n vertices, a neighborhood subtree is defined as the set of all points on the tree within a certain radius of a given point, called the center. It is shown that for any two neighborhood subtrees containing the same endpoint of a longest path in the tree one is contained in the other. This result is then used to obtain O(n²) algorithms for the minimum cost covering problem and the minimum cost operating problem as well as an O(n³) algorithm for the uncapacitated plant location problem on the tree.     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.