Approximation Algorithms For The Problems Related To The Edge Vertex Domination Set In Graphs

In this paper,three variant problems of edge vertex domination set problem are studied:the submodular edge vertex domination set problem with linear penalties,the partial edge vertex domination set problem and the partial capacitated edge vertex domination set problem.In the submodular edge vertex domination set problem with linear penalties,we are given a graph G=(V,E),a submodular function c:2E→R≥0 and a penalty function p:V→R≥0.The goal of the problem is to find an edge subset D such that the sum of the weight of D and the penalties of vertices undominated by D is minimized.In this paper,we first give the integer programming of the problem,its relaxed linear programming and the corresponding dual programming.Then,based on the adjusted dual programming we design an approximation algorithm.Besides,we prove that its approximation ratio is k,where k=maxv∈V{|N[v]|} with N[v]being the closed neighborhood of the vertex v.In the partial edge vertex domination set problem,we are given a graph G=(V,E),a function c:E→R≥0 and an integer s.The goal of the problem is to find an edge subset D where the number of vertices undominated by D is less than or equal to s and the weight of D is minimized.In this paper,we first give an integer programming of the problem,its relaxed linear programming and the corresponding dual programming.Then,based on the dual programming,a two-step approximation algorithm including pruning and dual updating is designed.Finally,we prove the approximate ratio of the algorithm is l,where l=maxv∈V{|{e:N[v]∩e ≠(?)}|}.In the partial capacitated edge vertex domination set problem,we are given a graph G=(V,E)and an integer s,where each edge e∈E is associated with a non-negative weight ce and a capacity ke,and can be selected repeatedly.The goal of the problem is to find an edge subset D such that the number of vertices undominated by D is less than or equal to s and Σe∈D cexe is minimized,where xe is the chosen times of e.In this paper,we first give an integer programming of the problem,its relaxed linear programming and the corresponding dual programming.Then,an approximation algorithm is designed.Finally,we prove the approximate ratio of the algorithm is l(l is defined as above).