A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

New analysis and computational study for the planar connected dominating set problem

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt{n}}n+n^3)\) time and \(O(2^{8.11\sqrt{n}}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt{n}}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt{n}}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \({\hbox {bw}}(G)\) be the branchwidth of \(G\) and \(\gamma _c(G)\) be the connected dominating number of \(G\). We prove \({\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.     

A greedy algorithm for the fault-tolerant connected dominating set in a general graph

Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to an accidental damage or energy depletion, it is desirable that the virtual backbone is fault tolerant. A node set \(C\) is an \(m\) -fold connected dominating set ( \(m\) -fold CDS) of graph \(G\) if every node in \(V(G)\setminus C\) has at least \(m\) neighbors in \(C\) and the subgraph of \(G\) induced by \(C\) is connected. In this paper, we will present a greedy algorithm to compute an \(m\) -fold CDS in a general graph, which has size at most \(2+\ln (\Delta +m-2)\) times that of a minimum \(m\) -fold CDS, where \(\Delta \) is the maximum degree of the graph. This result improves on the previous best known performance ratio of \(2H(\Delta +m-1)\) for this problem, where \(H(\cdot )\) is the Harmonic number.     

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

A heuristic approximation algorithm of minimum dominating set based on rough set theory

The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set.

     

Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

A PTAS for minimum weighted connected vertex cover $$P_3$$ problem in 3-dimensional wireless sensor networks

Given a connected and weighted graph \(G=(V, E)\) with each vertex v having a nonnegative weight w(v), the minimum weighted connected vertex cover \(P_{3}\) problem \((MWCVCP_{3})\) is required to find a subset C of vertices of the graph with minimum total weight, such that each path with length 2 has at least one vertex in C, and moreover, the induced subgraph G[C] is connected. This kind of problem has many applications concerning wireless sensor networks and ad hoc networks. When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. In this paper, we propose a new concept called weak c-local and give the first polynomial time approximation scheme (PTAS) for \(MWCVCP_{3}\) in unit ball graphs when the weight is smooth and weak c-local.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

A simple approximation algorithm for minimum weight partial connected set cover

Let \(LTQ_n\) be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in \(LTQ_n\). Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex \(v(\ne r)\), the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that \(LTQ_n\) fails to be vertex-transitive for \(n\geqslant 4\) and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in \(LTQ_n\). Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in \(LTQ_n\) in \({\mathcal O}(n)\) time using \(2^n\) vertices of \(LTQ_n\) as processors.     

PTAS for minimum weighted connected vertex cover problem with <Emphasis Type="Italic">c</Emphasis>-local condition in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺, the minimum weighted connected vertex cover problem (MWCVC) is to seek a subset of vertices of the graph with minimum total weight, such that for any edge of the graph, at least one endpoint of the edge is contained in the subset, and the subgraph induced by this subset is connected. In this paper, we study the problem on unit disk graph. A polynomial-time approximation scheme (PTAS) for MWCVC is presented under the condition that the graph is c-local.     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

Independent dominating sets in triangle-free graphs

The independent domination number of a graph is the smallest cardinality of an independent set that dominates the graph. In this paper we consider the independent domination number of triangle-free graphs. We improve several of the known bounds as a function of the order and minimum degree, thereby answering conjectures of Haviland.     

Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs

For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP₂) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP₂ problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP₂ problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.     

Sparse multipartite graphs as partition universal for graphs with bounded degree

For graphs G and H, let \(G\rightarrow (H,H)\) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote \(\mathcal {H}(\Delta ,n)=\{H:|V(H)|=n,\Delta (H)\le \Delta \}\). For any \(\Delta \) and n, we say that G is partition universal for \(\mathcal {H}(\Delta ,n)\) if \(G\rightarrow (H,H)\) for every \(H\in \mathcal {H}(\Delta ,n)\). Let \(G_r(N,p)\) be the random spanning subgraph of the complete r-partite graph \(K_r(N)\) with N vertices in each part, in which each edge of \(K_r(N)\) appears with probability p independently and randomly. We prove that for fixed \(\Delta \ge 2\) there exist constants r, B and C depending only on \(\Delta \) such that if \(N\ge Bn\) and \(p=C(\log N/N)^{1/\Delta }\), then asymptotically almost surely \(G_r(N,p)\) is partition universal for \(\mathcal {H}(\Delta ,n)\).     

Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs

Journal of Combinatorial Optimization - Let G be a simple graph, where each vertex has a nonnegative weight. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of...