论文标题
图中2秒统治的算法方面
Algorithmic Aspects of 2-Secure Domination in Graphs
论文作者
论文摘要
令$ g（v，e）$为简单，无向和连接的图。如果每一对独特的顶点$ u_1，u_1，u_2 \ in v（g）$，则在$ g $中的主导集$ s \ subseteq v（g）$称为$ 2 $ - \ textit {secure dimprating set}（$ 2 $ -sds）（$ g $） \在n [u_2] $和$（s \ setMinus \ {v_1，v_2 \}）\ cup \ {u_1，u_2 \} $是$ g $中的主导集。 $ 2 $ \ textIt { - Secure Doymination number}用$γ_{2S}（G）$表示，等于$ G $中的$ 2 $ -SD的最低基数。鉴于图$ g $和一个正整数$ k，$ 2 $ secure的统治（$ 2 $ -sdm）的问题是检查$ g $是否具有$ 2 $ -secure的$ 2 $ -Secure主导型$K。$。在本文中，我们证明了$ 2 $ -sdm的问题对于平面图和双弦图（串联图）是NP库。我们通过证明此问题是二分组图的NP完整结果，即二分组的NP完整结果，即恒星凸两部分，梳子凸凸双方图。我们证明，$ 2 $ -sdm是可以解决有限树宽度图的线性时间。我们还表明，即使对于拆分图，$ 2 $ -sdm也是w [2] -hard。最低$ 2 $ -SECURE主导集（M2SD）问题是在输入图中找到最小尺寸的$ 2 $ SECURE主导集。我们建议使用M2SD的$δ（g）+1 $ - $ - $ - $近似算法，其中$δ（g）$是输入图$ g $的最大程度，并证明M2SD不能在$（1-ε）\ ln（| v |）$中近似于任何$> $> $ε> np ogim> vim v | |）}）$。即使是两分图的％。图形\ textit {feffers}在图的任何顶点上的一组攻击}的安全主导集。最后，我们证明M2SD是$δ（g）= 4的图形的APX算法。$
Let $G(V,E)$ be a simple, undirected and connected graph. A dominating set $S \subseteq V(G)$ is called a $2$-\textit{secure dominating set} ($2$-SDS) in $G$, if for every pair of distinct vertices $u_1,u_2 \in V(G)$ there exists a pair of distinct vertices $v_1,v_2 \in S$ such that $v_1 \in N[u_1]$, $v_2 \in N[u_2]$ and $(S \setminus \{v_1,v_2\}) \cup \{u_1,u_2 \}$ is a dominating set in $G$. The $2$\textit{-secure domination number} denoted by $γ_{2s}(G)$, equals the minimum cardinality of a $2$-SDS in $G$. Given a graph $ G$ and a positive integer $ k,$ the $ 2 $-Secure Domination ($ 2 $-SDM) problem is to check whether $ G $ has a $ 2 $-secure dominating set of size at most $ k.$ It is known that $ 2 $-SDM is NP-complete for bipartite graphs. In this paper, we prove that the $ 2 $-SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We strengthen the NP-complete result for bipartite graphs, by proving this problem is NP-complete for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite graphs. We prove that $ 2 $-SDM is linear time solvable for bounded tree-width graphs. We also show that the $ 2 $-SDM is W[2]-hard even for split graphs. The Minimum $ 2 $-Secure Dominating Set (M2SDS) problem is to find a $ 2 $-secure dominating set of minimum size in the input graph. We propose a $ Δ(G)+1 $ $ - $ approximation algorithm for M2SDS, where $ Δ(G) $ is the maximum degree of the input graph $ G $ and prove that M2SDS cannot be approximated within $ (1 - ε) \ln(| V | ) $ for any $ ε> 0 $ unless $ NP \subseteq DTIME(| V |^{ O(\log \log | V | )}) $. % even for bipartite graphs. A secure dominating set of a graph \textit{defends} one attack at any vertex of the graph. Finally, we show that the M2SDS is APX-complete for graphs with $Δ(G)=4.$
