Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight ω(v). A multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

Capacitated Domination Problem

We consider a generalization of the well-known domination problem on graphs. The (soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.     

Static Frequency Assignment in Cellular Networks

A cellular network is generally modeled as a subgraph of the triangular lattice. In the static frequency assignment problem, each vertex of the graph is a base station in the network, and has associated with it an integer weight that represents the number of calls that must be served at the vertex by assigning distinct frequencies per call. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicoloring problem. We describe an efficient algorithm to multicolor optimally any weighted even or odd length cycle representing a cellular network. This result is further extended to any outerplanar graph. For the problem of multicoloring an arbitrary connected subgraph of the triangular lattice, we demonstrate an approximation algorithm which guarantees that no more than 4/3 times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each station needs to have knowledge only of the weights at a small neighborhood. Received May 13, 1997; revised August 24, 1998.     

Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight (v). A multicoloring of G is to assign each vertex v a set of (v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

An effective heuristic algorithm for sum coloring of graphs

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G, using colors represented by natural numbers (1,2,…) such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP-hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.     

The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC

In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O(log n) parallel algorithm with polynomially many processors on the CRCW model.     

Approximation Algorithms for Connected Dominating Sets

The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c _n +1) \ln n where c _n ln k is the approximation factor for the node weighted Steiner tree problem (currently c _n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ). Received June 22, 1996; revised February 28, 1997.     

Convex recolorings of strings and trees: Definitions, hardness results and algorithms

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one, and what are the convex colorings which are “closest” to it. In this paper we study a natural definition of this distance—the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number cost(v,d). Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree.     

A branch‐and‐price approach to k‐clustering minimum biclique completion problem

We consider the problem of finding k‐bipartite subgraphs, called “clusters,” in a bipartite graph , such that each vertex i of S appears in exactly one of the subgraphs, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to complete each cluster (i.e. to become a biclique) is minimized. This problem has been shown to be strongly NP‐hard and is known as the k‐clustering minimum biclique completion problem. It has been applied to bundling channels for multicast transmissions. The application consists of finding k‐multicast sessions that partition the set of demands, given a set of demands of services from clients. Each service should belong to a single multicast session, while each client can appear in more than one session. We extend previous work by developing a branch‐and‐price algorithm that embeds a new metaheuristic based on variable neighborhood infeasible search and a branching rule that exploits the problem structure. The metaheuristic can also efficiently solve the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated using the MovieLens dataset collected by the GroupLens Research Project. Extensive computational results show that our branch‐and‐price algorithm outperforms the approaches proposed in the literature.     

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

Flexible coloring

Motivated by reliability considerations in data deduplication for storage systems, we introduce the problem of flexible coloring. Given a hypergraph H and the number of allowable colors k, a flexible coloring of H is an assignment of one or more colors to each vertex such that, for each hyperedge, it is possible to choose a color from each vertex?s color list so that this hyperedge is strongly colored (i.e., each vertex has a different color). Different colors for the same vertex can be chosen for different incident hyperedges (hence the term flexible). The goal is to minimize color consumption, namely, the total number of colors assigned, counting multiplicities. Flexible coloring is NP-hard and trivially approximable, where s is the size of the largest hyperedge, and n is the number of vertices. Using a recent result by Bansal and Khot, we show that if k is constant, then it is UGC-hard to approximate to within a factor of s−ε, for arbitrarily small constant ε>0. Lastly, we present an algorithm with an approximation ratio, where k^′ is number of colors used by a strong coloring algorithm for H.     

A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs

A subset F of vertices of a graph G is called a vertex cover P_k set if every path of order k in G contains at least one vertex from F. Denote by ψ_k(G) the minimum cardinality of a vertex cover P_k set in G. The vertex cover P_k (VCP_k) problem is to find a minimum vertex cover P_k set. It is easy to see that the VCP₂ problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP₄ problem in cubic graphs. The paper proves that the VCP₄ problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ₄(G) for cubic graphs and propose a 2-approximation algorithm for the VCP₄ problem in cubic graphs.     

A NEW APPROACH TO THE VERTEX COLORING PROBLEM

The vertex coloring problem is a well-known classical optimization problem in graph theory in which a color is assigned to each vertex of the graph in such a way that no two adjacent vertices have the same color. The minimum vertex coloring problem is known to be an NP-hard problem in an arbitrary graph, and a host of approximation solutions are available. In this article, a learning automata–based approximation algorithm is proposed to solve the minimum vertex coloring problem. The proposed algorithm iteratively finds the different possible colorings of the graph and compares it at each stage with the best coloring found so far. If the number of distinct colors in the chosen coloring is less than that of the best coloring, the chosen coloring is rewarded; otherwise, it is penalized. Convergence of the proposed algorithm to the optimal solution is proven. The proposed vertex coloring algorithm is compared with the well-known coloring techniques and the results show the superiority of the proposed algorithm over the others both in terms of the color set size and running time of algorithm.     

An exact algorithm for minimizing vertex guards on art galleries

We consider the problem [art gallery problem (AGP)] of minimizing the number of vertex guards required to monitor an art gallery whose boundary is an n‐vertex simple polygon. In this paper, we compile and extend our research on exact approaches for solving the AGP. In prior works, we proposed and tested an exact algorithm for the case of orthogonal polygons. In that algorithm, a discretization that approximates the polygon is used to formulate an instance of the set cover problem, which is subsequently solved to optimality. Either the set of guards that characterizes this solution solves the original instance of the AGP, and the algorithm halts, or the discretization is refined and a new iteration begins. This procedure always converges to an optimal solution of the AGP and, moreover, the number of iterations executed highly depends on the way we discretize the polygon. Notwithstanding that the best known theoretical bound for convergence is Θ(n³) iterations, our experiments show that an optimal solution is always found within a small number of them, even for random polygons of many hundreds of vertices. Herein, we broaden the family of polygon classes to which the algorithm is applied by including non‐orthogonal polygons. Furthermore, we propose new discretization strategies leading to additional trade‐off analysis of preprocessing vs. processing times and achieving, in the case of the novel Convex Vertices strategy, the most efficient overall performance so far. We report on experiments with both simple and orthogonal polygons of up to 2500 vertices showing that, in all cases, no more than 15 minutes are needed to reach an exact solution, on a standard desktop computer. Ultimately, we more than doubled the size of the largest instances solved to optimality compared with our previous experiments, which were already five times larger than those previously reported in the literature.     

Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

A memetic algorithm for the Minimum Sum Coloring Problem

Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002–2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 15 instances.     

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.

1.

The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C_v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C_v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2.

An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists.

3.

The list chromatic numberχ_l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L_v of colors, where each list has length at least r, there is a choice of one color from each vertex list L_v yielding a proper coloring of G. We show that the problem of determining whether χ_l(G)?r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

     

Adaptive decentralized finite‐time output tracking control for MIMO interconnected nonlinear systems with output constraints and actuator faults

In this work, we present a novel adaptive decentralized finite‐time fault‐tolerant control algorithm for a class of multi‐input–multi‐output interconnected nonlinear systems with output constraint requirements for each vertex. The actuator for each system can be subject to unknown multiplicative and additive faults. Parametric system uncertainties that model the system dynamics for each vertex can be effectively dealt with by the proposed control scheme. The control input gain functions of the nonlinear systems can be not fully known and state dependent. Backstepping design with a tan‐type barrier Lyapunov function and a new structure of stabilizing function is presented. We show that under the proposed control scheme, with the use of graph theory, finite‐time convergence of the system output tracking error into a small set around zero is guaranteed for each vertex, while the time‐varying constraint requirement on the system output tracking error for each vertex will not be violated during operation. An illustrative example on 2 interacting 2‐degree‐of‐freedom robot manipulators is presented in the end to further demonstrate the effectiveness of the proposed control scheme.     

Solving the multi-vehicle multi-covering tour problem

The well-known multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route is covered. Here, a vertex is considered as covered if it lies within a given distance of at least a vertex of a route. This article introduces a generalized variant of the m-CTP that we called the multi-vehicle multi-covering Tour Problem (mm-CTP). In the mm-CTP, a vertex must be covered at least not only once but several times. Three variants of the problem are considered. The binary mm-CTP where a vertex is visited at most once, the mm-CTP without overnight where revisiting a vertex is allowed only after passing through another vertex and the mm-CTP with overnight where revisiting a vertex is permitted without any restrictions. We first propose graph transformations to convert the last two variants into the binary one and focus mostly on solving this variant. A special case of the problem is then formulated as an integer linear program and a branch-and-cut algorithm is developed. We also develop a Genetic Algorithm (GA) that provides high-quality solutions for the problem. Extensive computational results on the new problem mm-CTP as well as its other special cases show the performance of our methods. In particular, our GA outperforms the current best metaheuristics proposed for a wide class of CTP problems.