2023/10/11 by Debojyoti Bhattacharya, Bhattacharya, Debojyoti, Subhabrata Paul +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2310.07452
openalex publication_date 2023/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a simple undirected graph. The open neighbourhood of a vertex v in G is defined as NG(v)=\u∈ V~|~ uv∈ E\; whereas the closed neighbourhood is defined as NG[v]= NG(v)∪ \v\. For an integer k, a subset D⊆ V is called a k-vertex-edge dominating set of G if for every edge uv∈ E, |(NG[u]∪ NG[v]) ∩ D|≥ k. In k-vertex-edge domination problem, our goal is to find a k-vertex-edge dominating set of minimum cardinality of an input graph G. In this paper, we first prove that the decision version of k-vertex-edge domination problem is NP-complete for chordal graphs. On the positive side, we design a linear time algorithm for finding a minimum k-vertex-edge dominating set of tree. We also prove that there is a O(log(Δ(G)))-approximation algorithm for this problem in general graph G, where Δ(G) is the maximum degree of G. Then we show that for a graph G with n vertices, this problem cannot be approximated within a factor of (1-ε) ln n for any ε>0 unless NP⊆ DTIME(|V|O(loglog|V|)). Finally, we prove that it is APX-complete for graphs with bounded degree k+3.