Algorithmic study on liar’s vertex-edge domination problem

Debojyoti Bhattacharya () and Subhabrata Paul ()
Additional contact information
Debojyoti Bhattacharya: Indian Institute of Technology Patna
Subhabrata Paul: Indian Institute of Technology Patna

Journal of Combinatorial Optimization, 2024, vol. 48, issue 3, No 10, 18 pages

Abstract: Abstract Let $$G=(V,E)$$ G = ( V , E ) be a graph. For an edge $$e=xy\in E$$ e = x y ∈ E , the closed neighbourhood of e, denoted by $$N_G[e]$$ N G [ e ] or $$N_G[xy]$$ N G [ x y ] , is the set $$N_G[x]\cup N_G[y]$$ N G [ x ] ∪ N G [ y ] . A vertex set $$L\subseteq V$$ L ⊆ V is liar’s vertex-edge dominating set of a graph $$G=(V,E)$$ G = ( V , E ) if for every $$e_i\in E$$ e i ∈ E , $$|N_G[e_i]\cap L|\ge 2$$ | N G [ e i ] ∩ L | ≥ 2 and for every pair of distinct edges $$e_i$$ e i and $$e_j$$ e j , $$|(N_G[e_i]\cup N_G[e_j])\cap L|\ge 3$$ | ( N G [ e i ] ∪ N G [ e j ] ) ∩ L | ≥ 3 . This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph G, the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of G of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We show that MinLVEDP can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for general graphs, chordal graphs, and bipartite graphs. We further study approximation algorithms for this problem. We propose two approximation algorithms for MinLVEDP in general graphs and p-claw free graphs. On the negative side, we show that the MinLVEDP cannot be approximated within $$\frac{1}{2}(\frac{1}{8}-\epsilon )\ln |V|$$ 1 2 ( 1 8 - ϵ ) ln | V | for any $$\epsilon >0$$ ϵ > 0 , unless $$NP\subseteq DTIME(|V|^{O(\log (\log |V|)})$$ N P ⊆ D T I M E ( | V | O ( log ( log | V | ) ) . Finally, we prove that the MinLVEDP is APX-complete for bounded degree graphs and p-claw-free graphs for $$p\ge 6$$ p ≥ 6 .

Keywords: Liar’s vertex-edge dominating set; NP-completeness; Approximation algorithms; Chordal graphs; Bipartite graphs; 05C85; 05C05; 05C69 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01208-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:3:d:10.1007_s10878-024-01208-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01208-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().