Algorithmic aspects of b-disjunctive domination in graphs

For a fixed integer $$b>1$$ b > 1 , a set $$D\subseteq V$$ D ⊆ V is called a b-disjunctive dominating set of the graph $$G=(V,E)$$ G = ( V , E ) if for every vertex $$v\in V{\setminus }D$$ v ∈ V \ D , v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by $$\gamma _{b}^{d}(G)$$ γ b d ( G ) . Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, $$\gamma _{b}^{d}(G)$$ γ b d ( G ) is equal to $$\gamma (G)$$ γ ( G ) , the domination number of G for $$b \ge 3$$ b ≥ 3 and observe that $$\gamma _{b}^{d}(G)$$ γ b d ( G ) need not be equal to $$\gamma (G)$$ γ ( G ) for $$b=2$$ b = 2 . We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for $$b=2$$ b = 2 . Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a $$(\ln ({\varDelta }^{2}+(b-1){\varDelta }+b)+1)$$ ( ln ( Δ 2 + ( b - 1 ) Δ + b ) + 1 ) -approximation algorithm for MbDDP, where $${\varDelta }$$ Δ is the maximum degree of input graph $$G=(V,E)$$ G = ( V , E ) and prove that MbDDP cannot be approximated within $$(1-\epsilon ) \ln (|V|)$$ ( 1 - ϵ ) ln ( | V | ) for any $$\epsilon >0$$ ϵ > 0 unless NP $$\subseteq $$ ⊆ DTIME $$(|V|^{O(\log \log |V|)})$$ ( | V | O ( log log | V | ) ) . Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree $$\max \{b,4\}$$ max { b , 4 } .