Improved Approximations for Weighted and Unweighted Graph Problems

We obtain improved approximation ratios for problems of a broad class called weighted hereditary induced-subgraph maximization problems, in particular for the maximum independent set, maximum clique and maximum ℓ-colorable induced subgraph, as well as for the minimum coloring problem. We also study the minimum chromatic sum and show that its weighted version polynomially reduces to the weighted independent set problem in such a way that approximation ratios are preserved (up to a multiplicative constant).     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

Polyhedral Characteristics of Balanced and Unbalanced Bipartite Subgraph Problems

We study the polyhedral properties of three problems of constructing an optimal complete bipartite subgraph (a biclique) in a bipartite graph. In the first problem, we consider a balanced biclique with the same number of vertices in both parts and arbitrary edge weights. In the other two problems we are dealing with unbalanced subgraphs of maximum and minimum weight with non-negative edges. All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. We describe the adjacency criterion in the 1-skeleton of the polytope of the balanced complete bipartite subgraph problem. The clique number of the 1-skeleton is estimated from below by a superpolynomial function. For both unbalanced biclique problems we establish the superpolynomial lower bounds on the clique numbers of the graphs of nonnegative cone decompositions. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.     

The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

The lexicographically first maximal (lfm) subgraph problem for a property is to compute the lfm vertex set whose induced subgraph satisfies . The main contribution of this paper is theP-completeness of the lfm subgraph problem for any nontrivial hereditary property. We also observe that most of the lfm subgraph problems are stillP-complete even if the instances are restricted to graphs with degree 3. However, some exceptions are found. For example, it is shown that the lfm 4-cycle free subgraph problem is inNC ² for graphs with degree 3 but turns out to beP-complete for graphs with degree 4. Further, we analyze the complexity of the lfmedge-induced subgraph problem for some graph properties and show that it has a different complexity feature.This work was done while the author visited Universität-GH-Paderborn and a part of this paper was presented at the 14th ICALP, Karlsruhe, 1987.     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.     

A Hopfield network learning method for bipartite subgraph problem

We present a gradient ascent learning method of the Hopfield neural network for bipartite subgraph problem. The method is intended to provide a near-optimum parallel algorithm for solving the bipartite subgraph problem. To do this we use the Hopfield neural network to get a near-maximum bipartite subgraph, and increase the energy by modifying weights in a gradient ascent direction of the energy to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm. We also test the learning method on total coloring problem. The simulation results show that our method finds optimal solution in every test graph.     

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.     

Design and analysis of maximum Hopfield networks

Since McCulloch and Pitts presented a simplified neuron model (1943), several neuron models have been proposed. Among them, the binary maximum neuron model was introduced by Takefuji et al. and successfully applied to some combinatorial optimization problems. Takefuji et al. also presented a proof for the local minimum convergence of the maximum neural network. In this paper we discuss this convergence analysis and show that this model does not guarantee the descent of a large class of energy functions. We also propose a new maximum neuron model, the optimal competitive Hopfield model (OCHOM), that always guarantees and maximizes the decrease of any Lyapunov energy function. Funabiki et al. (1997, 1998) applied the maximum neural network for the n-queens problem and showed that this model presented the best overall performance among the existing neural networks for this problem. Lee et al. (1992) applied the maximum neural network for the bipartite subgraph problem showing that the solution quality was superior to that of the best existing algorithm. However, simulation results in the n-queens problem and in the bipartite subgraph problem show that the OCHOM is much superior to the maximum neural network in terms of the solution quality and the computation time.     

An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-hard problems in graph and set theory via clique finding.

Many graph- and set-theoretic problems, because of their tremendous application potential and theoretical appeal, have been well investigated by the researchers in complexity theory and were found to be NP-hard. Since the combinatorial complexity of these problems does not permit exhaustive searches for optimal solutions, only near-optimal solutions can be explored using either various problem-specific heuristic strategies or metaheuristic global-optimization methods, such as simulated annealing, genetic algorithms, etc. In this paper, we propose a unified evolutionary algorithm (EA) to the problems of maximum clique finding, maximum independent set, minimum vertex cover, subgraph and double subgraph isomorphism, set packing, set partitioning, and set cover. In the proposed approach, we first map these problems onto the maximum clique-finding problem (MCP), which is later solved using an evolutionary strategy. The proposed impatient EA with probabilistic tabu search (IEA-PTS) for the MCP integrates the best features of earlier successful approaches with a number of new heuristics that we developed to yield a performance that advances the state of the art in EAs for the exploration of the maximum cliques in a graph. Results of experimentation with the 37 DIMACS benchmark graphs and comparative analyses with six state-of-the-art algorithms, including two from the smaller EA community and four from the larger metaheuristics community, indicate that the IEA-PTS outperforms the EAs with respect to a Pareto-lexicographic ranking criterion and offers competitive performance on some graph instances when individually compared to the other heuristic algorithms. It has also successfully set a new benchmark on one graph instance. On another benchmark suite called Benchmarks with Hidden Optimal Solutions, IEA-PTS ranks second, after a very recent algorithm called COVER, among its peers that have experimented with this suite.     

The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem

Several classes of sequential algorithms to approximate themaximum acyclic subgraph problem are examined. The equivalentfeedback arc set problem isNP-complete and there are only a few classes of graphs for which it is known to be inP. Thus, approximation algorithms are very important for this problem. Our goal is to determine how effectively the various sequential algorithms parallelize. Of the sequential algorithms we study, natural decision problems based on several of them are provedP-complete. Parallel implementations usingO(log ¦V¦) time and ¦E¦ processors on an EREW PRAM exist for the other algorithms. Interestingly, the parallelizable algorithms appear very similar to some of theinherently sequential algorithms. Thus, for approximating the maximum acyclic subgraph problem small algorithmic changes drastically alter parallel complexity, unlessNC equalsP.     

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a complete picture for the case with a single forbidden connected (induced or noninduced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path with at least one edge, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles. In particular, we prove that it is NP-complete to decide if a planar graph can be 2-colored so that no cycle of length at most 5 is monochromatic.     

A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

The maximum planarization problem is to find a spanning planar subgraph having the largest number of edges for a given graph. In this paper, we propose a self-stabilizing algorithm to solve this problem for complete bipartite networks. The proposed algorithm finds the maximum planar subgraph of 2n−4 edges in O(n) rounds, where n is the number of nodes.     

Clique-perfectness and balancedness of some graph classes

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.     

最小权度的网络构建问题

网络构建问题是组合最优化中的经典问题．而连通性是网络设计问题中的一个核心问题。考虑这样一个最优化问题：给定无向图G=（V,E;W）,W：E→Q^＋是权重函数,G’=（V,E’）为G的一个子图．要寻找E的一个子集E”E．使得由E’∪E”所得的诱导子图是一个连通图,其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析．对问题的特殊情况E’=Ф,设计了两个时间复杂度分别为O（n^2）和O（mn）的启发式算法。而E”≠Ф的情况也可以类似讨论．     

Two‐node‐connected star problem

In this study, a two‐node‐connected star problem (2NCSP) is introduced. We are given a simple graph and internal and external costs for each link of the graph. The goal is to find the minimum‐cost spanning subgraph, where the core is two‐node‐connected and the remaining external nodes are connected to the core. First, we show that the 2NCSP belongs to the class of NP‐hard computational problems. Therefore, a greedy randomized adaptive search procedure (GRASP) heuristic is developed, enriched with a variable neighborhood descent (VND). The neighborhood structures include exact integer linear programming models to find the best paths and two‐node‐connected replacements, as well as a shaking operation in order to prevent being trapped in a local minima. The ring star problem (RSP) represents a relevant model in network optimization, where the core is a ring instead of an arbitrary two‐node‐connected graph. We contrast our GRASP/VND methodology with a previous reference work on the RSP in order to highlight the effectiveness of our heuristic. The heuristic is competitive, and the best results produced for several instances so far are under study. In this study, a discussion of the results and trends for future work are provided.     

Necessary and sufficient conditions of risk‐sensitive optimal control and differential games for stochastic differential delayed equations

In this paper, we consider risk‐sensitive optimal control and differential games for stochastic differential delayed equations driven by Brownian motion. The problems are related to robust stochastic optimization with delay due to the inherent feature of the risk‐sensitive objective functional. For both problems, by using the logarithmic transformation of the associated risk‐neutral problem, the necessary and sufficient conditions for the risk‐sensitive maximum principle are obtained. We show that these conditions are characterized in terms of the variational inequality and the coupled anticipated backward stochastic differential equations (ABSDEs). The coupled ABSDEs consist of the first‐order adjoint equation and an additional scalar ABSDE, where the latter is induced due to the nonsmooth nonlinear transformation of the adjoint process of the associated risk‐neutral problem. For applications, we consider the risk‐sensitive linear‐quadratic control and game problems with delay, and the optimal consumption and production game, for which we obtain explicit optimal solutions.     

基于加权网络和局部适应度的蛋白质复合物识别算法

蛋白质复合物识别对分析蛋白质网络的结构特征和模块功能具有重要意义。通常在蛋白质网络中挖掘稠密子图或模块来识别其中的蛋白质复合物,限制了其应用范围和识别的准确性。针对该问题,提出了一种基于加权网络和局部适应度的蛋白质复合物识别算法,该算法综合稠密子图的密度指标和模块性定义了新的局部适应度函数,并基于边聚集系数构建加权的蛋白质网络,根据权值选择边,在加权蛋白质网络中将种子边不断聚类扩展,从而获取具有最大综合适应度的子图作为蛋白质复合物。在酵母蛋白质等多个实际网络中试验表明,该算法能够有效提升蛋白质复合物识别的准确性。     

Energy function-based approaches to graph coloring

We describe an approach to optimization based on a multiple-restart quasi-Hopfield network where the only problem-specific knowledge is embedded in the energy function that the algorithm tries to minimize. We apply this method to three different variants of the graph coloring problem: the minimum coloring problem, the spanning subgraph k-coloring problem, and the induced subgraph k-coloring problem. Though Hopfield networks have been applied in the past to the minimum coloring problem, our encoding is more natural and compact than almost all previous ones. In particular, we use k-state neurons while almost all previous approaches use binary neurons. This reduces the number of connections in the network from (Nk)(2) to N(2) asymptotically and also circumvents a problem in earlier approaches, that of multiple colors being assigned to a single vertex. Experimental results show that our approach compares favorably with other algorithms, even nonneural ones specifically developed for the graph coloring problem.     

Maximum planar subgraphs and nice embeddings: Practical layout tools

In automatic graph drawing a given graph has to be laid out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard.We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good, and in many cases provably optimum, solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graphG is defined and studied. All subgraphs of a graphG, which are subdivisions ofK ₅ orK _3,3, turn out to define facets of this polytope. For cliques contained inG, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover, we introduce the subdivision inequalities,V _2k inequalities, and the flower inequalities, all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated.We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision ofK ₅ orK _3,3. These structures give us inequalities which are used as cutting planes.Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An Ω(n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.