Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game

Weighted vertex cover(WVC)is one of the most important combinatorial optimization problems.In this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks.We first model the WVC problem as a general game on weighted networks.Under the framework of a game,we newly define several cover states to describe the WVC problem.Moreover,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums(SNEs)of the game.Then,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time.Subsequently,we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms,termed the improved game-based asynchronous algorithm(IGAA),in which we prove that it can obtain a better solution to the WVC problem than using a the GAA.Finally,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

New Hybrid Genetic Algorithm for Vertex Cover Problems

This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.

A Heuristic Approach to Fast NOVCA （Near Optimal Vertex Cover Algorithm）

This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.

(g,f)-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE (mg,mf)-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.

Approximation Algorithm for Weighted Weak Vertex Cover

The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work. Keywords weak vertex cover - NP-hard - approximation algorithm NoteThis work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.

On the Vertex Cover Number of 3-Uniform Hypergraph

Given a hypergraph H(V,E),a set of vertices S⊆V is a vertex cover if every edge has at least one vertex in S.The vertex cover number is the minimum cardinality of a vertex cover,denoted byτ(H).In this paper,we prove that for every 3-uniform connected hypergraph H(V,E),τ(H)≤2m3+1/3 holds on where m is the number of edges.Furthermore,the equality holds on if and only if H(V,E)is a hypertree with perfect matching.

An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem

We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.

Second Powers of Cover Ideals of Paths

We show that the second power of the cover ideal of a path graph has linear quotients.To prove our result we construct a recursively defined order on the generators of the ideal which yields linear quotients.Our construction has a natural generalization to the larger class of chordal graphs.This generalization allows us to raise some questions that are related to some open problems about powers of cover ideals of chordal graphs.

Algebraic Characterization of SSC of Uni-Cyclic Multigraphs

We introduce first the spanning simplicial complex(SSC)of a multigraph g,which gives a generalization of the SSC associated with a simple graph G.Combinatorial properties are discussed for the SSC of a family of uni-cyclic multigraphs U_(n)^(r),m with n edges including r multiple edges within and outside the cycle of length m,which are then used to compute the f-vector and Hilbert series of face ring k[△s(U_(n)^(r),m)]for the SSC △s(U_(n)^(r),m)(un,m).Moreover,we find the associated primes of the facet ideal I_(F)(△s(U_(n)^(r),m).Finally,we device a formula for homology groups of △s(U_(n)^(r),m) prove that the SsC of a family of uni-cyclic multigraphs is Cohen-Macaulay.

The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.

The NF-Number of a Simplicial Complex

Let△bea simplicial complex on[n].TheNF-complex of△is the simplicial complexδ_(NF)(△)on[n]for which the facet ideal of△is equal to the Stanley-Reisner ideal ofδ_(NF)(△).Furthermore,for each k=2,3,....,we introduce the kth NF-complexδ_(NF)^(k)(△),which is inductively defined asδ_(NF)(k)(△)=δ_(NF)(δ_(NF)^(k-1)(△))by settingδ_(NF)^(1)(△)=δ_(NF)(△).One canδ_(NF)^(0)(△)=△.The NF-number of△is the smallest integer k>0 for whichδ_(NF)^(k)(△)■△.In the present paper we are especilly interested in the NF-number of a finite graph,which can be regraded as a simplicial complex of dimension one.It is shown that the NF-number of the finite graph K_(n)■K_(m)on[n+m],which is the disjoint union of the complete graphs K_(n)on[n]and K_(m)on[m]for n≥2 and m≥2 with(n,m)≠(2,2),is equal to n+m+2.As a corollary,we find that the NF-number of the complete bipartite graph K_(n,m)on[n+m]is also equal to n+m+2.