key: cord-0044042-5abiajbm
authors: Lamprou, Ioannis; Sigalas, Ioannis; Zissimopoulos, Vassilis
title: Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_28
sha: ebf414ccf287276083b1d9357aed41338696ebad
doc_id: 44042
cord_uid: 5abiajbm

We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k, we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous [Formula: see text] approximation in [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a [Formula: see text] approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to [Formula: see text]. On the other hand, we prove a [Formula: see text] inapproximability bound, for any [Formula: see text]. We also examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we are given a graph G, and a budget k, and we seek a, not necessarily connected, subset of k edges such that the number of dominated vertices in G is maximized. We prove there exists a [Formula: see text]-approximation algorithm. Also, for any [Formula: see text], we present a [Formula: see text]-inapproximability result by a gap-preserving reduction from the maximum coverage problem. Finally, we examine the “dual” Partial Edge-Vertex Domination (PEVD) problem, where a graph G and a quota [Formula: see text] are given. The goal is to select a minimum-size set of edges to dominate at least [Formula: see text] vertices in G. In this case, we present a [Formula: see text]-approximation algorithm by a reduction to the partial cover problem.

The problem of vertices dominating vertices in a graph is very common and has been extensively studied in graph theory and combinatorial optimization literature. In the classical definition, a dominating set is a subset of vertices such that each vertex is either a member of the subset or adjacent to a member of the subset. Intuitively, a dominating set provides a skeleton for the placement of resources, such that any network node is within immediate reach to them.

However, as it is often the case, there are constraints on the amount of resources available for placement, e.g., due to financial or other management reasons. That is, we are limited to a budget of k resources to be placed on network nodes. The optimization goal is to place the available resources suitably, such that the number of network nodes they dominate is maximized. This problem is known in literature as the Budgeted Dominating Set problem.

Budgeted domination has applications especially in ad-hoc wireless (sensor) networks. In this setting, a set of network nodes needs to be identified as the virtual backbone of the network, that is, the structure responsible for routing and packet forwarding. To achieve these tasks, nodes in the backbone must be able to communicate with each other, i.e., form a connected set of vertices in the graph capturing the topology of their communication ranges. The resulting optimization problem is the Budgeted Connected Dominating Set (BCDS) problem. In this paper, we study BCDS and present an improved guarantee over the previous state of the art [12] .

Besides BCDS, we examine other problems where graph edges are selected as dominators. The concept of edges dominating adjacent edges has been wellconsidered in literature; e.g., see [8, 27] for some preliminary results. An example application is in network tomography where probes need to be placed to monitor the health of network links [14] .

In this paper, we consider cases where resources must be positioned on the links of a network to dominate network nodes. For instance, consider a power system where a limited number of static var compensators need to be placed on transmission lines' midpoints to locate faults affecting a big proportion of buses [10] . Another example is to identify a limited-size set of friendships, modeled as graph edges, having a big impact in terms of neighborhood in a social network.

More formally, the notion in consideration is edge-vertex domination, where an edge dominates its endpoints and any vertices adjacent to its endpoints. We examine the (in)approximability of Budgeted Edge-Vertex Domination (BEVD), where we seek a, not necessarily connected, set of k (budget) edges dominating as many vertices as possible. If the edge set is required to be connected, we show that the problem essentially matches BCDS. Finally, we consider the related Partial Edge-Vertex Domination (PEVD) problem: a quota of vertices needs to be dominated by utilizing the minimum number of edges possible.

Finding a minimum-size connected set of vertices dominating the whole graph is a classical NP-hard problem. In [7] , Guha and Khuller proposed a ln Δ + 3 approximation algorithm, which is (up to constant factors) the best possible, since the problem is hard to approximate within a factor of (1 − ) log n [5] . For a bigger picture of the research landscape, in [4] , many connected domination results for special graph classes and other applications are surveyed.

In [21] , vertex-vertex and edge-edge budgeted domination are considered. For vertex-vertex, matching upper and lower bounds of (1 − 1/e) are given, whereas, for edge-edge, a (1−1/e) approximation and a 1303/1304+ hardness are proved.

In the connected case, budgeted and partial versions of domination have their origins in wireless sensor networking [19, 26] , where a network backbone with good qualities needs to be determined, which must either be limited in resources and/or cover a big-enough proportion of the network. The first, and thus far state of the art, results for the budgeted and partial cases in general graphs appear in [12] , where a (1 − 1/e)/13-approximation, respectively an O(ln Δ)-approximation, is proved for the budgeted, respectively partial, case. Other works have followed in particular settings. For example, in [20] , a constant factor approximation algorithm for partial connected domination on a superset of unit disk graphs, namely growth-bounded graphs, is proposed. Their result translates to a 27-approximation guarantee on unit disk graphs.

Regarding edge-vertex domination, the graph-theoretic notion was introduced in [22] , together with the complementary case of vertex-edge domination, where a vertex dominates all edges incident to it or to a neighbor of it. Some complexity and algorithmic results about the minimal size of an edge-vertex, respectively vertex-edge, dominating set appear in [18] . More recently, some vertex-edge domination open questions posed in [18] were answered in [2] . In [25] , an improved bound on the edge-vertex domination number of trees was proved. Except for the vertex-edge and edge-vertex variants, a mixed domination variant has been introduced [23] , where a minimal subset of both vertices and edges need to be selected so that each vertex/edge of the graph is incident/adjacent to a vertex/edge in the subset. Recent example works in this topic study the problem in special graph classes like trees, cacti, and split graphs [17, 28] .

In Sect. 2, we present preliminary notions and formally define the problems.

In Sect. 3, we examine the Budgeted Connected Dominating Set (BCDS) problem, see Definition 1, where a connected subset of budget vertices needs to dominate as many vertices as possible. By introducing a new tree decomposition technique in Subsect. 3.2, we prove a (1 − 1/e)/12 0.05267 approximation, in Theorem 2, which improves over the previous best known (1−1/e)/13 guarantee [12] . (We note the same guarantee has recently been achieved independently in [13] .) We further improve the ratio to (1 − e −7/8 )/11 0.05301 (Theorem 3) by generalizing the first part of the analysis in [12] and then modifying the proposed algorithm accordingly in Subsect. 3.3. On the negative side, for any > 0, we show a first (1 − 1/e + ) inapproximability bound; see Theorem 5.

In Sect. 4, we consider edge-vertex domination, where a, not necessarily connected, subset of edges dominates adjacent vertices. If the set of edges is also required to be connected, then the problems essentially reduce to the standard vertex-vertex budgeted/partial dominating set problems; see Proposition 2. In Subsect. 4.1, we prove there is a (1−1/e)-approximation algorithm (Theorem 7). This is the best possible since we prove an (1 − 1/e + ) inapproximability lower bound, for any > 0, see Theorem 8. In Subsect. 4.2, we consider the problem of Partial Edge-Vertex Domination. In Theorem 10, we prove that, in the general case, there exists an H(n )-approximation, where H(·) is the Harmonic number and n is the number of vertices requested to be dominated. To do so, we employ a reduction to a partial version of the classical Set Cover problem.

Finally, in Sect. 5, we give some concluding remarks.

A graph G is denoted as a pair (V (G), E(G)) (or simply (V, E)) of the vertices and edges of G. The graphs considered are simple (neither loops nor multiedges are allowed), connected and undirected. Besides the aforementioned, no assumptions are made on the topology of the input graphs.

Let us now consider the neighborhood of edges in terms of vertices. Given an edge e = (v, u) ∈ E, let I(e) = {v, u} stand for the set containing its two incident vertices. We define the neighborhood of an edge e as

Here, we focus on a closed neighborhood definition, since it captures the number of vertices incident or adjacent to a set of edges in the standard edge-vertex domination paradigm (Definition 8 in [18] ; originally introduced in [22] ). That is, we say that a set of edges E dominates N [E ].

Let us now proceed to formally define the problems studied in this paper.

Given a graph G = (V, E) and an integer k, select a subset S ⊆ V , where |S| ≤ k, such that the subgraph induced by S is connected and |N [S]| is maximized.

k, select a subset E ⊆ E, where |E | ≤ k, such that |N [E ]| is maximized.

Given a graph G = (V, E) and an integer n , select a subset E ⊆ E of minimum size such that it holds |N [E ]| ≥ n .

In this section, we consider the Budgeted Connected Dominating Set (BCDS) problem given in Definition 1. We initially present a summary of key aspects of the state of the art algorithm [12] , which achieves a (1 − 1/e)/13 approximation factor. We then show how the analysis can be improved to achieve a (1− 1/e)/12 guarantee via an alternative tree decomposition scheme; see Theorem 2. Then, we generalize the analysis of the greedy procedure in order to modify a call within the state of the art algorithm. This modification allows us to increase the approximation factor even further to (1 − e −7/8 )/11; see Corollary 1. On the other hand, we conclude this section with a (1 − 1/e + ), for any > 0, inapproximability result; see Theorem 5.

Khuller et al., see Algorithm 2 (Algorithm 5.1 in [12] ), design the first constant factor approximation algorithm for BCDS with an approximation guarantee of (1 − 1/e)/13. Their approach comprises three method calls: (i) a call to an algorithm returning a greedy dominating set D and its corresponding profit function p; see Algorithm 1 (GDS), (ii) a call to a 2-approximation algorithm, which follows from [6, 9] , for the Quota Steiner Tree (QST) problem defined below, and (iii) a call to a dynamic programming scheme Best k (·) to determine the maximum-profit subtree of size at most k within a bigger-size tree.

Algorithm 1: Greedy Dominating Set (GDS) [12] Input : A graph G = (V (G), E(G)) Output: A dominating set D ⊆ V (G) and a profit function Algorithm 2: Greedy Profit Labeling Algorithm for BCDS [12] Input : A graph G = (V (G), E(G)) and k ∈ N Output: A treeT on at most k vertices

Theorem 1 (Follows from results in [6, 9] ). There is a 2-approximation algorithm for QUOTA STEINER TREE.

In their analysis, Khuller et al. [12] demonstrate that there exists a set D ⊆ D of size k which dominates at least (1 − 1/e)OPT vertices, where OPT is the optimal number of dominated vertices achieved with a budget of k. Furthermore, D can be connected by adding at most another 2k Steiner vertices, so giving a total of 3k vertices. Then, it suffices to call the 2-approximation algorithm for QST, see line 2 in Algorithm 2, with profit function p (returned by algorithm GDS at line 1), all edge costs equal to 1 and quota equal to (1 − 1/e)OPT. The value OPT can be guessed via a binary search between k and n. Overall, the returned tree has size at most 6k vertices and dominates at least (1 − 1/e)OPT vertices: a (6, 1 − 1/e) bicriteria approximation is attained (Lemma 5.2 [12] ).

As a final step (Best k (·) at line 3), a dynamic programming approach is used to identify the best-profit subtree with at most k vertices, such that the budget requirement is satisfied; see paragraph 5.2.2 in [12] for the relevant recurrences. To obtain a true approximation guarantee for the final solution, the following tree decomposition lemma is used recursively to prove that, for a sufficiently large value of k, a tree of size 6k can be decomposed into 13 trees; each of size at most k (Lemma 5.4 [12] ).

Given any tree on n vertices, we can decompose it into two trees (by replicating a single vertex) such that the smaller tree has at most n 2 vertices and the larger tree has at most 2n 3 vertices.

An improvement to the analysis in [12] can be achieved by utilising a more refined tree decomposition (than the recursive application of Lemma 1) to provide the approximation guarantee at the final step. To do so, we consider a tree decomposition scheme based on the notion of eligible trees as introduced in [3] .

Given a directed tree T = (V T , E T ), an eligible subtree T is a subtree of T rooted at some vertex i ∈ V T such that the forest obtained by deleting the edges with both endpoints in T , and then all the remaining vertices of degree 0, consists of a single tree.

Assuming T is an eligible subtree not identical to T , after deleting all edges with both endpoints in T , the only vertex of T with degree strictly greater than 0 is the root vertex of T . That is, like in Lemma 1, a single vertex is replicated when removing T from T ; see Fig. 1 . The following lemma suggests that, for any tree, there exists an eligible subtree within some specific size range. Lemma 2 (Lemma 5 [3] ). For each directed tree T = (V T , E T ), and for each p ∈ [1, |V T |]∩N, there exists an eligible subtree T of T such that p/2 ≤ |V T | ≤ p. Fig. 1 . An example eligible subtree of size 6 (enclosed within the dashed shape). After removing its edges and then all remaining vertices of degree 0 (vertices with lines), a single tree remains (enclosed within the solid shape). A single vertex is replicated in both trees, the black vertex.

We can now proceed to employ the above lemma iteratively toward a decomposition scheme for the tree of size at most 6k returned by the Quota Steiner Tree call in Algorithm 2. Proof. To make T directed, we orient its edges away from some arbitrary vertex picked as the root. Now, we iteratively apply Lemma 2 with p = k, until we are left with a tree on at most k vertices.

First, let us show that after i iterations, the remaining tree has at most ak − i · (k/2 − 1) vertices. At the first iteration, there exists an eligible subtree T 1 such that k/2 ≤ |V T 1 | ≤ k. After removing it from T 1 := T we are left with T 2 of size |V T1 | − (|V T 1 | − 1), since the root of T 1 remains in T 1 . Hence, |V T1 | ≤ ak − (k/2 − 1), since k/2 ≤ |V T 1 |. Assume that after i iterations of the above procedure, it holds for the remaining tree T i+1 that k < |V Ti+1 | ≤ ak−i·(k/2−1). We inductively apply Lemma 2 with p = k and get an eligible subtree T i+1 .

We proved that, after i removals of eligible subtrees from the original tree, for the remaining tree

which is at most k for a sufficiently large value of k, i.e., k ≥ 4a − 2. Overall, the original tree T 1 has been decomposed into 2a trees: T 1 , T 2 , . . . , T 2a−1 and T 2a , each of which has at most k vertices. Theorem 2. Algorithm 2 is a (1 − 1/e)/12 approximation for BCDS.

In the following proof, we generalize the analysis given in Lemma 5.1 [12] regarding the existence of a greedily selected set (of at most k vertices) with a good intersection to the (neighborhood of the) optimal solution. Below, let D and p refer to the dominating set and profit function returned by GDS (line 1 in Algorithm 2). Proof. We define the layers L 1 , L 2 , L 3 as follows. L 1 contains the (at most k) vertices of an optimal BCDS solution. Let L 2 = N (L 1 ), meaning that the optimal number of dominated vertices is OPT = |L 1 ∪ L 2 |. Also, let L 3 = N (L 2 ) \ L 1 and R = V \ (L 1 ∪ L 2 ∪ L 3 ), where R denotes the remaining vertices, i.e., those outside the three layers L 1 , L 2 , L 3 . Let us now consider the intersection of these layers with the greedy dominating set D returned by GDS (Algorithm 1). Let L i = D ∩ L i for i = 1, 2, 3 and D = {v 1 , v 2 , . . . , v λ } denote the first λ = ck vertices from L 1 ∪ L 2 ∪ L 3 in the order selected by the greedy algorithm. In order to bound the total profit in D , we define g i = i μ=1 p(v μ ) as the profit we gain from the first i vertices of D . For the initial value, let g 0 = 0. Proposition 1 (Claim 1 [12] ).

By solving the recurrence in Claim 1, we get

OPT. Moreover, let us show that an extra k + ck vertices are enough to ensure that D is connected. We select a subset D ⊆ L 2 of size at most |L 3 ∩D | ≤ ck to dominate all vertices of D ∩L 3 . Then, we ensure that all vertices are connected by simply adding all the k vertices of L 1 . Thus,D = D ∪ D ∪ L 1 induces a connected subgraph that contains at most k + 2 ck vertices.

We can now make use of this generalized analysis and suggest a modified algorithm, parameterized by the parameter c, where the Quota Steiner Tree routine is called with a quota of (1 − e −c )OPT; see Algorithm 3 below.

Proof. By Lemma 4 and Theorem 1, it follows that Algorithm 3 (line 2) returns a tree of size at most 2k + 4 ck ≤ 2k + 4(ck + 1) = (4c + 2)k + 4 with profit at least (1 − e −c )OPT. For a final solution, it suffices to return a subtree of T , namely T , of size at most k which dominates the maximum number of vertices (call Best k (·) in line 3 of Algorithm 3). This can be done in polynomial time via dynamic programming: see section 5.2.2 in [12] .

To prove a lower bound on the number of vertices T dominates, we decompose T into a set of subtrees via iteratively removing an eligible tree from T . To do so, we apply Lemma 2 with p = k. Like in the proof of Lemma 3, we can prove by induction that after i such removals of eligible subtrees of size at most k, the remaining tree has at most |T | − i · (k/2 − 1) vertices. For i = 8c + 3 , the remaining tree's size is upper bounded by (4c + 2)k + 4 − 8c + 3 · (k/2 − 1) ≤ (4c + 2)k + 4 − (8c + 3) · (k/2 − 1) = k/2 + 8c + 7, which is at most k for a sufficiently large choice of k, i.e., k ≥ 16c + 14. Therefore, we can decompose T into 8c + 3 + 1 = 8c + 4 subtrees of size at most k, say T 1 , T 2 , . . . , T 8c +4 . Then, from pigeonhole principle and our decomposition, it

For c = 1, Theorem 3 matches the approximation ratio already given in Theorem 2. Since the above ratio is a function of the parameter c, we numerically compute its maximum value to 1/11(1 − e −7/8 ) attained for c = 7/8.

There is a 1/11(1 − e −7/8 )-approximation for BCDS.

In this Subsection, we demonstrate a first inapproximability result for BCDS by identifying a reduction from the well known Maximum Coverage problem. Overall, |V | = m + qn. In the edge set E, we include edges (s i , s j ), for each i, j = 1, 2, . . . , m, i = j, and (s i , x j,z ), for each i, j such that x j ∈ S i and for each z = 1, 2, . . . , q. Notice the size is polynomial in the input of MC(S, k), since we get |E| ≤ m 2 + mqn. In Lemma 5, let MC(S, k), respectively BCDS(G, k), also refer to the optimal solution for the corresponding MAX-k-COVER, resp. BCDS, instance. 

s 1 s 2 s i s m · · · · · · · · · · · · .

We now turn our attention to edge-vertex domination problems, where the goal is to identify a set of edges which dominate vertices of the graph. We consider both budgeted and partial cover cases.

Let us consider the general case of BEVD (Definition 2), where the selected subset of edges does not need to be connected. We identify a strong connection to the classical MAX-k-COVER problem; see Definition 6 and Theorems 4, 6. On the positive side, in Theorem 7, we prove a (1 − 1/e)-approximation by reducing BEVD to an instance of MAX-k-COVER. On the negative side, we demonstrate a gap-preserving reduction from MAX-k-COVER to BEVD and therefore conclude that the above approximation is the best possible (Theorem 8).

Theorem 6 (Proposition 5.1 [5] ). There exists a (1 − 1/e)-approximation algorithm in polynomial time for MAX-k-COVER.

There exists a (1 − 1/e)-approximation algorithm for BEVD.

We now proceed and demonstrate a gap-preserving reduction (Definition 10.2 [1] ) which transforms an instance of MAX-k-COVER, namely MC(S, k), where S = {S 1 , S 2 , . . . , S m } to an instance of BEVD, namely BEVD(G, k), where G = (V, E). For an illustration, see Fig. 3 . The vertex set V contains a "root" vertex v 0 . For each set S i ∈ S, we include a vertex s i in V . Let the union of elements in the set system Si∈S S i be represented as {x 1 , x 2 , . . . , x n }. For each element x j , we include q vertices in V , namely x j,1 , x j,2 , . . . , x j,q , where q is a polynomial in m (q ≥ m 2 suffices) Overall, we have |V | = m+1+qn. In the edge set E, we include the edges (v 0 , s i ), for each i = 1, 2, . . . , m, and (s i , x j,z ), for each i, j such that x j ∈ S i and for each z = 1, 2, . . . , q. The size is polynomial in the input of MC(S, k), since we get |E| ≤ m + mqn. In Lemma 6, let MC(S, k), respectively BEVD(G, k), refer to the optimal solution for the corresponding max cover, resp. BEVD, instance.

There is a gap-preserving reduction from MAX-k-COVER to BEVD so that,

For any > 0, there is no polynomial time approximation algorithm for BEVD within a ratio of (1 − 1/e + ) unless P = NP.

As a side note, consider the case where the selected edge set is required to be connected. That is, let BEVD C refer to the budgeted edge-vertex connected domination problem. Below, we prove that this problem is equivalent to the budgeted connected dominating set (BCDS) problem researched in Sect. 3 . 

Herein, we prove an O(log n)-approximation for Partial Edge-Vertex Domination (PEVD); refer to Definition 3. Given a graph G = (V, E) and an integer n , we need to select a subset E ⊆ E of minimum size such that it holds |N [E ]| ≥ n .

To approximate the problem, we identify a reduction to Partial Cover (PC). 

We propose a new technique to obtain tree decompositions, and a generalized analysis, thus improving the approximation guarantee from (1 − e −1 )/13 to (1 − e −7/8 )/11 for BCDS. Furthermore, we prove a (1 − 1/e + ) upper bound. Also, we introduce BEVD and PEVD, and provide (tight) approximation bounds. Regarding future work on BCDS, the goal is to design an algorithm with an improved guarantee. Moreover, it would be interesting to capture the difficulty of the problem with a stronger inapproximability result. We believe that a tight bound lies somewhere between our currently established state of the art.

Related to the edge-vertex case, it would be interesting to consider budgeted and partial versions for other dominating set variants, such as mixed domination [28] , where both vertices and edges are selected in order to dominate as many vertices and edges as possible, expansion ratio variants such as in [16] , or even eternal domination [15] , where a set of guards need to dominate the graph perpetually while moving to protect it against attacks on its vertices.

Hardness of approximations

Vertex-edge domination in graphs

Bin packing with colocations

Connected Dominating Set: Theory and Applications

Springer Optimization and its Applications

A threshold of ln n for approximating set cover

Saving an epsilon: a 2-approximation for the k-MST problem in graphs

Approximation algorithms for connected dominating sets

Minimum edge dominating sets

The prize collecting Steiner tree problem: theory and practice

Locating fault on transmission line with static var compensator based on phasor measurement unit

The budgeted maximum coverage problem

Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems

Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems

Efficient beacon placement for network tomography

Eternally dominating large grids

Maximum rooted connected expansion

On the mixed domination problem in graphs

Vertex-edge and edge-vertex parameters in graphs

Approximate coverage in wireless sensor networks

The first constant factor approximation for minimum partial connected dominating set problem in growth-bounded graphs

Maximum domination problem

Theoretical and algorithmic results on domination and connectivity

Mixed domination in graphs

Improved performance of the greedy algorithm for partial cover

An improved upper bound of edgevertex domination number of a tree

Coverage problems in sensor networks

Edge dominating sets in graphs

The algorithmic complexity of mixed domination in graphs