Let $G=(V,E)$ be a graph. For an edge $e=xy\in E$, the closed neighbourhood of $e$, denoted by $N_G[e]$ or $N_G[xy]$, is the set $N_G[x]\cup N_G[y]$. A vertex set $L\subseteq V$ is liar's vertex-edge dominating set of a graph $G=(V,E)$ if for every $e_i\in E$, $|N_G[e_i]\cap L|\geq 2$ and for every pair of distinct edges $e_i$ and $e_j$, $|(N_G[e_i]\cup N_G[e_j])\cap L|\geq 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 \textsc{Minimum Liar's Vertex-Edge Domination Problem} (\textsc{MinLVEDP}) asks to find a liar's vertex-edge dominating set of $G$ of minimum cardinality. In this paper, we study this problem from algorithmic point of view. We show that \textsc{MinLVEDP} can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for chordal graphs, bipartite graphs, and $p$-claw free graphs for $p\geq 4$. We further study approximation algorithms for this problem. We propose two approximation algorithms for \textsc{MinLVEDP} in general graphs and $p$-claw free graphs. %We propose an $O(\ln \Delta(G))$-approximation algorithm for \textsc{MinLVEDP} in general graphs, where $\Delta(G)$ is the maximum degree of the input graph. Also, we design a constant factor approximation algorithm for $p$-claw free graphs. On the negative side, we show that the \textsc{MinLVEDP} cannot be approximated within $\frac{1}{2}(\frac{1}{8}-\epsilon)\ln|V|$ for any $\epsilon >0$, unless $NP\subseteq DTIME(|V|^{O(\log(\log|V|)})$. Finally, we prove that the \textsc{MinLVEDP} is APX-complete for bounded degree graphs and $p$-claw free graphs for $p\geq 6$.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
学习自然语言处理路线图
专知会员服务
137+阅读 · 2019年9月24日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
论文浅尝 | 利用 RNN 和 CNN 构建基于 FreeBase 的问答系统
开放知识图谱
11+阅读 · 2018年4月25日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关资讯
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
论文浅尝 | 利用 RNN 和 CNN 构建基于 FreeBase 的问答系统
开放知识图谱
11+阅读 · 2018年4月25日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员