An Improved Derandomized Approximation Algorithm for the Max-Controlled Set Problem

Carlos Alberto Martinhon^{1} and Fábio Protti^{2}

1 Instituto Computação Universidade Federal Fluminense Rua Passo da Pátria 156, Bloco E, Sala 303 24210-230, Niterói, RJ, Brasil

                      mart@dcc.ic.uff.br

2 IM and NCE, Universidade Federal do Rio de Janeiro Caixa Postal 2324, 20001-970, Rio de Janeiro, RJ, Brasil

                      fabiop@nce.ufrj.br

Abstract. A vertex i of a graph G = (V, E) is said to be controlled by M ⊆ V if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex i ∈ V is controlled by M. Given a set M ⊆ V and two graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) where E_{1} ⊆ E_{2}, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V, E) (i.e., a graph where E_{1} ⊆ E ⊆ E_{2}) such that M is a monopoly in G = (V, E). If the answer to the mvp is No, we then consider the max-controlled set problem (mcsp), whose objective is to find a sandwich graph G = (V, E) such that the number of vertices of G controlled by M is maximized. The mvp can be solved in polynomial time; the mcsp, however, is NP-hard. In this work, we present a deterministic polynomial time approximation algorithm for the mcsp with ratio \frac{1}{2} + \frac{1+\sqrt{n}}{2n−2} , where n = |V | > 4. (The case n ≤ 4 is solved exactly by considering the parameterized version of the mcsp.) The algoritm is obtained through the use of randomized rounding and derandomization techniques, namely the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance. Keywords: Randomized Rounding, Monte Carlo Method, Sandwich Problems, Derandomization.

1 Preliminaries

Given two graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) such that E_{1} ⊆ E_{2}, we say that G = (V, E), where E_{1} ⊆ E ⊆ E_{2}, is a sandwich graph for some property Π if G = (V, E) satisfies Π. A sandwich problem consists of deciding whether there exists some sandwich graph satisfying Π. Many different properties may be considered in this context. In general, the property Π is non-hereditary by (not induced) subgraphs (otherwise G_{1} would trivially be a solution, if any) and non-ancestral by supergraphs (otherwise G_{2} would trivially be a solution, if any.) As discussed by Golumbic et al. [7], sandwich problems generalize recognition problems arising in various situations (when G_{1} = G_{2}, the sandwich problem becomes simply a recognition problem.)

One of the most known sandwich problems is the chordal sandwich problem, where we require G to be a chordal graph (a graph where every cycle of length at least four possesses a chord - an edge linking two non-consecutive vertices in the cycle). The chordal sandwich problem is closely related to the minimum fill-in problem [19]: given a graph G, find the minimum number of edges to be added to G so that the resulting graph is chordal. The minimum fill-in poblem has applications to areas such as solution of sparse systems of linear equations [15]. Another important sandwich problem is the interval sandwich problem, where we require the sandwich graph G to be an interval graph (a graph whose vertices are in a one-to-one correspondence with intervals on the real line in such a way that there exists an edge between two vertices if and only if the corresponding intervals intersect.) Kaplan and Shamir [8] describe applications to DNA physical mapping via the interval sandwich problem. In this work we consider a special kind of sandwich problem, the max-controlled set problem (mcsp) [11], which is described in the sequel.

Given an undirected graph G = (V, E) and a set of vertices M ⊆ V, a vertex i ∈ V is said to be controlled by M if |N_{G}[i] ∩ M| ≥ |N_{G}[i]|/2, where N_{G}[i] = {i} ∪ {j ∈ V |(i, j) ∈ E}. The set M defines a monopoly in G if every vertex i ∈ V is controlled by M. Following the notation of [11], if cont(G, M) denotes the set of vertices controlled by M in G, M will be a monopoly in G if and only if cont(G, M) = V.

In order to defined formally the mcsp, we first define the monopoly verification problem (mvp) : given a set M ⊆ V and two graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}), where E_{1} ⊆ E_{2}, the question is to decide whether there exists a set E such that E_{1} ⊆ E ⊆ E_{2} and M is a monopoly in G = (V, E). If the answer of the mvp applied to M, G_{1}, and G_{2} is No, we then consider the mcsp, whose goal is to find a set E such that E_{1} ⊆ E ⊆ E_{2} and the number of vertices controlled by M in G = (V, E) is maximized.

The mvp can be solved in polynomial time by formulating it as a network flow problem [11]. If the answer to the mvp is No, then a natural alternative is to solve the mcsp. Unfortunately, the mcsp is NP-hard, even for those instances where G_{1} is an empty graph and G_{2} is a complete graph. In [11] a reduction from independent set to the mcsp is given. In the same work, an approximation algorithm for the mcsp with ratio \frac{1}{2} is presented.

The notion of monopoly has applications to local majority voting in distributed environments and agreement in agent systems [1, 6, 10, 13, 16, 17]. For instance, suppose that the agents must agree on one industrial standard between two proposed candidate standards. Suppose also that the candidate standard supported by the majority of the agents is to be selected. When every agent knows the opinion of his neighbors, a natural heuristic to obtain a reasonable agreement is: every agent i takes the majority opinions in N[i]. This is known as the deterministic local majority polling system. In such a system, securing the support by the members of a monopoly M implies securing unanimous agreement. In this context, the motivation for the mcsp is to find an efficient way of controlling the maximum number of objects by modifying the system’s topology.

In this work, we present a linear integer programming formulation and a randomized rounding procedure for the mcsp. As far as we know, our procedure achieves the best polynomial time approximation ratio for the mcsp. If y^{∗} denotes the optimum value of the linear relaxation and y^{∗} > A(k) (for some fixed k ∈ (1, 2] and some function A(k) > 4), the approximation ratio \frac{1}{k} + \frac{1+\sqrt{y^{∗}}}{k(y^{∗}−1)} improves the \frac{1}{2}-approximation algorithm presented in [11]. As described later, the case y^{∗} ≤ A(k) may be solved exactly by considering a polynomial time algorithm for the parameterized version of the mcsp. This procedure is based on the ideas presented in [11] for the mvp.

This paper is organized as follows. In Section 2 some basic notation and results from [11] are presented. These are fundamental for the development of our algorithm. In Section 3, we introduce the parameterized mcsp. For a given parameter A ≥ 0, we solve exactly the parameterized mcsp in time O(n^{A}). Section 4 gives a detailed description of our mcsp formulation and outlines our randomized rounding procedure. In randomized rounding techniques, we first solve the linear relaxation and “round” the resulting solution to produce feasible solutions. In Section 5 we present an approximation analysis via the probabilistic method (introduced by Erdös and Spencer [5]). In this case, the main objective is to construct probabilistic existence proofs of some particular combinatorial structure for actually exhibiting this structure. This is performed through the use of derandomization techniques. In Section 6 we describe a derandomized procedure via the method of conditional expectations, achieving an improved deterministic approximation algorithm for the mcsp with performance ratio \frac{1}{2} + \frac{1+\sqrt{n}}{2n−2}. Finally, in Section 7, we present some conclusions and suggestions for future work.

2 The \frac{1}{2}-approximation algorithm for the mcsp by Makino et al.

Consider a maximization optimization problem P and an arbitrary input instance I of P. Denote by ẑ(I) the optimal objective function value for I, and by z_{H}(I) the value of the objective function delivered by an algorithm H. Without loss of generality, it is assumed that each feasible solution for I has a non-negative objective function value. Recall that H is a φ-approximation algorithm for P if and only if a feasible solution of value z_{H}(I) ≥ φẑ(I) is delivered for all instances I and some φ satisfying 0 < φ ≤ 1.

From now on, we suppose that the answer for the mvp when applied to M, G_{1} and G_{2} is No. Let us briefly describe the deterministic \frac{1}{2}-approximation algorithm for the mcsp presented in [11]. For A, B ⊆ V, define the edge set D(A, B) = {(i, j) ∈ E_{2}\E_{1} | i ∈ A, j ∈ B}. Let U = V \M. Two reduction rules are used: a new edge set E_{1}^{∗} is obtained by the union of E_{1} and D(M, M), and a new edge set E_{2}^{∗} is obtained by removing D(U, U) from E_{2}. Since we are maximizing the total number of vertices controlled by M, these reduction rules do not modify the optimal solution. In other words, the edge set E in the sandwich graph G satisfies E_{1} ∪ D(M, M) ⊆ E ⊆ E_{1} ∪ D(M, M) ∪ D(U, M).

For simplicity, assume from now on E_{1} = E_{1}^{∗} (Reduction Rule 1) and E_{2} = E_{2}^{∗} (Reduction Rule 2). In the MYK algorithm, W 1, W 2 ⊆ V denote the sets of vertices controlled by M in G = (V, E) for E = E_{1} and E = E_{2}, respectively.

Algorithm 1: MYK algorithm [11]

1. compute |W_{1}| by removing from G_{2} the edge set D(U, M)

2. compute |W_{2}| by adding to G_{1} the edge set D(U, M)

3. z_{H} ← max{|W_{1}|, |W_{2}|}

Formally, they proved the following result:

Theorem 1. The value z_{H} returned by Algorithm 1 satisfies z_{H}(I) ≥ \frac{1}{2} ẑ(I), for all instances I of the mcsp.

3 Parameterizing the mcsp

In this Section we introduce the parameterized mcsp. Let A be a fixed nonnegative integer. The objective is to find, in polynomial time, a solution for the mcsp with value at least A. In other words, we require the parameter A to be a lower bound for the maximum number of vertices that can be controlled by M in a sandwich graph G = (V, E) with E_{1} ⊆ E ⊆ E_{2}.

Let us describe an O(n^{A}) algorithm for the parameterized mcsp. We first consider a partition of V into six special subsets (some of them are implicitly described in [11]):

– M_{C} and U_{C}, consisting of the vertices in M and U, respectively, which are controlled by M in any sandwich graph (vertices which are “always controlled”);

– M_{N} and U_{N}, consisting of the vertices in M and U, respectively, which are not controlled by M in any sandwich graph (vertices which are “never controlled”);

– M_{R} and U_{R}, defined as M_{R} = M\(M_{C} ∪ M_{N}) and U_{R} = U\(U_{C} ∪ U_{N}).

Define the binary variables x_{ij} ∈ {0, 1} for i, j ∈ V and assume that x_{ij} = x_{ji}, ∀i, j ∈ V. Define binary constants a_{ij} ∈ {0, 1} such that a_{ij} = 1 if and only if i = j or (i, j) ∈ E_{2}. Consider now the following auxiliary equations:

B_{i} = ∑_{j∈M} a_{ij}x_{ij} − ∑_{j∈U} a_{ij}x_{ij}, for i = 1, …, |V |  (1)

In these equations, assume that: x_{ii} = 1 for every i ∈ V, x_{ij} = 1 for every (i, j) ∈ E_{1}, and x_{ij} = 0 for every (i, j) ∉ E_{2}. This means that the remaining binary variables are associated to edges in E_{2}\E_{1} (set of optional edges). It is clear that B_{i} ≥ 0 for some 0-1 assignment (to variables associated to optional edges) if and only if vertex i can be controlled by M in some sandwich graph. Observe that the subsets M_{C}, U_{C}, M_{N}, U_{N} can be thus characterized by the following properties:

– i ∈ M_{C} ∪ U_{C} if and only if B_{i} ≥ 0 for every 0-1 assignment;

– i ∈ M_{N} ∪ U_{N} if and only if B_{i} < 0 for every 0-1 assignment.

In fact, it is easy to construct these four sets, since it is sufficient to look at “worst-case” assignments. For instance, if i ∈ M then i ∈ M_{C} if and only if B_{i} ≥ 0 for a 0-1 assignment which sets x_{ij} = 1 for every (i, j) ∈ D({i}, U).

Use now the following new reduction rules:

– set x_{ij} = 1 for every (i, j) ∈ D(M_{C} ∪ M_{N}, U_{R}) (Reduction Rule 3);

– set x_{ij} = 0 for every (i, j) ∈ D(M_{R}, U_{C} ∪ U_{N}) (Reduction Rule 4);

– set arbitrary values to variables x_{ij} for (i, j) ∈ D(M_{C} ∪ M_{N}, U_{C} ∪ U_{N}) (Reduction Rule 5).

It is clear that if A ≤ |M_{C}|+|U_{C}| then the algorithm for the parameterized mcsp answers Yes. Hence, from now on, assume that A > |M_{C}| + |U_{C}|.

Clearly, M_{R} = Ø if and only if U_{R} = Ø. Thus, if M_{R} = Ø or U_{R} = Ø, the algorithm must answer No. Add then the assumption M_{R}, U_{R} ≠ Ø.

We fix an arbitrary subset S ⊆ M_{R} ∪U_{R} of cardinality |S| = A−|M_{C}|−|U_{C}|, and check whether it is possible to control S. Similarly to the reduction rules described above, set x_{ij} = 1 for every edge (i, j) ∈ D(M_{R}\S, U_{R} ∩ S), and x_{ij} = 0 for every edge (i, j) ∈ D(M_{R} ∩ S, U_{R}\S). Finally, set x_{ij} = 0 for every edge (i, j) ∈ D(M_{R} ∩ S, U_{R} ∩ S), and calculate the corresponding B_{i}’s according to equations (1).

Following the ideas in [11], we construct a network N whose vertex set consists of S together with two additional vertices s, t. Create an edge (s, i) with capacity B_{i} for every i ∈ S ∩M_{R}, an edge (j, t) with capacity B′_{j} = max{−B_{j}, 0} for every j ∈ S ∩ U_{R}, and an edge (i, j) with capacity 1 for every (i, j) ∈ D(S ∩ M_{R}, S ∩ U_{R}). Notice that N can be constructed in constant time, since its edge set contains at most O(A^{2}) elements. Now, if the maximum flow in N is equal to ∑_{j∈S∩U_{R}} B′_{j} then S can be controlled by selecting the edges of the form (i, j) ∈ D(S ∩ M_{R}, S ∩ U_{R}) with unitary flow value. This maximum flow problem can be solved in constant time, depending on A.

By repeating this procedure for every S ⊆ M_{R} ∪ U_{R} such that |S| = A − |M_{C}| − |U_{C}|, we obtain an algorithm with complexity O(n^{A}).

4 An improved randomized rounding procedure for the mcsp

The definition of performance ratio in randomized approximation algorithms is the same as in the deterministic ones. In this case, however, z_{H}(I) is replaced by E(z_{H}(I)), where the expectation is taken over the random choices made by the algorithm. Then, an algorithm H for a maximization problem is a randomized φ-approximation algorithm if and only if E(z_{H}(I)) ≥ φẑ(I) is delivered for all instances I and some 0 < φ ≤ 1.

In randomized rounding techniques (introduced by Raghavan and Thompson [14]), one usually solves a relaxation of a combinatorial optimization problem (by using linear or semidefinite programming), and uses randomization to return from the relaxation to the original optimization problem. The main idea is to use fractional solutions to define tuned probabilities in the randomized rounding procedure. Additional executions of this randomized procedure arbitrarily reduce the failure probability (Monte Carlo method).

In order to introduce a new integer programming formulation for the mcsp, we define the binary variables z_{i} for i ∈ V, which determine whether vertex i is controlled or not by M. Binary variables x_{ij} are used to decide whether optional edges belonging to E_{2}\E_{1} will be included or not in the sandwich graph. The objective function (2) computes the maximum number of controlled vertices. As defined before, binary constants a_{ij} ∈ {0, 1} are associated to edges (i, j) ∈ E_{2} with a_{ij} = 1 if and only if i = j or (i, j) ∈ E_{2}. (Assume that a_{ij} = a_{ji}, ∀i, j ∈ V.) Inequalities (3) guarantee that every time a vertex i is controlled by M, the left hand side will be greater than or equal to 1. On the other hand, if the left hand side is less than 1, vertex i will not be controlled by M and z_{i} will be set to 0. The divisions by n are used to maintain the difference between the two summations always greater than −1. Equalities (4) define the set of fixed edges. The linear programming relaxation is obtained by replacing integrality constraints (5) and (6) by x_{ij} ∈ [0, 1] and z_{i} ∈ [0, 1], respectively.

ẑ = max ∑_{i∈V} z_{i} (2)

subject to:

∑_{j∈M}(a_{ij}/n)x_{ij} − ∑_{j∈V} (a_{ij}/2n)x_{ij} + 1 ≥ z_{i}, ∀i ∈ V (3)

x_{ij} = 1, ∀(i, j) ∈ E_{1} (4)

x_{ij} ∈ {0, 1}, ∀(i, j) ∈ E_{2}\E_{1} (5)

z_{i} ∈ {0, 1}, ∀i ∈ V (6)

It is assumed from now on that (x^{∗}, z^{∗}) and y^{∗} will denote, respectively, an optimal solution of the relaxed integer programming formulation and its associated objective function value. The value of the original integer problem will be denoted by ẑ.

The value of linear programming relaxation may be improved if the reduction rules for the mcsp are used. As will be observed in Section 5, the performance ratio of our randomized algorithm is based on the value of the linear relaxation and an improvement of this ratio is attained if good upper bounds are obtained. Thus, assume without loss of generality that mcsp instances satisfy Reduction Rules 1 to 5.

Algorithm 2, based on randomized rounding techniques, is a Monte Carlo procedure and delivers, in polynomial time and with high probability, a value within a prescribed approximation ratio. In Step 3 of the algorithm we define a function A(k) for a given parameter k ∈ (1, 2] conveniently chosen. The construction of A(k) will be detailed in the next section. For the time being, an “oracle” is used.

Algorithm 2: randomized algorithm for the mcsp

1. compute z_{1} using Algorithm 1

2. solve the linear programming relaxation and return x^{∗} and y^{∗}

3. compute A(k) for some k ∈ (1, 2] (conveniently chosen)

4. if y^{∗} ≤ A(k)

then compute z_{H} by executing the algorithm for the parameterized mcsp in Section 3 for parameters A = ⌊y^{∗}⌋, ⌊y^{∗}⌋ − 1, …, 1, 0, until obtaining a Yes answer else for each (i, j) ∈ E_{2}\E_{1} do

P r(x̄_{ij} = 1) = x_{ij}^{∗} (constructing the integer feasible soluction) P r(x̄_{ij} = 0) = 1 − x_{ij}^{∗}

compute z_{2} by using the integer feasible function x̄

z_{H} ← max{z_{1}, z_{2}}

5. return z_{H}

We can use, for example, an interior point method in Step 2 (introduced by Karmarkar [9]) to compute the fractional solution x^{∗}, yielding in this way a polynomial time execution for Algorithm 2. Observe that Algorithm 2 always produce a feasible solution, and additional executions of Step 4 (for y^{∗} > A(k)) arbitrarily reduce the failure probability, provided that a prescribed approximation ratio is given. Moreover, it is obviously a \frac{1}{2}-approximation algorithm since Algorithm 1 was used in Step 1. As will be pointed out in the next section, this will directly help us to build an improved approximation algorithm with ratio \frac{1}{k} + \frac{1+\sqrt{y^{∗}}}{k(y^{∗}−1)} for some k ∈ (1, 2], conveniently chosen. It is straightforward to observe that, even for k = 2, this ratio is strictly greater than \frac{1}{2}, thus improving the previous result of [11]. In addition, recall that all those instances with y^{∗} ≤ A(k) (for some parameter A = ⌊y^{∗}⌋) are polinomially solved by the algorithm for the parameterized mcsp given in Section 3.

5 Approximation analysis

Before to proceed to the approximation analysis, consider the following auxiliary definitions and lemmas. We first present the notion of negative association.

Definition 1. (Negative Association) Let X = (X_{1}, X_{2}, …, X_{n}) be a vector of random variables. The random variables X are negatively associated if for every two disjoint index sets I, J ⊆ {1, 2, …, n}, E(f(X_{i}, i ∈ I)g(X_{j}, j ∈ J)) ≤ E(f(X_{i}, i ∈ I))E(g(X_{j}, j ∈ J)) for all functions f : ℜ^{|I|} → ℜ and g : ℜ^{|J|} → ℜ that are both non-decreasing and both non-increasing.

For a more detailed study concerning negative dependence see Dubhashi and Ranjan [4].

The next lemma ensures that the lower Chernoff-Hoeffding bound (lower CH bound) may be applied to not necessarily independent random variables. See Motwani and Raghavan [12] and Dubhashi and Ranjan [4] for the proof. An analogous result may be established for the upper CH bound.

Lemma 1. (Lower Chernoff-Hoeffding Bound and Negative Association) Let X_{1}, X_{2}, …, X_{n} be negatively associated Poisson trials such that, for 1 ≤ i ≤ n, P r(X_{i} = 1) = p_{i}, where 0 < p_{i} < 1. Then, for X = ∑_{i=1}^{n} X_{i}, μ = E(X) = ∑_{i=1}^{n} p_{i}, and any 0 < δ ≤ 1, we have that P r(X < (1 − δ)μ) < exp(−μδ^{2}/2).

Finally, consider the following auxiliary lemma:

Lemma 2. Let X, Y be arbitrary random variables. Then E(min(X, Y)) ≤ min(E(X), E(Y)).

Now, in order to describe the approximation analysis of Algorithm 2, we define random variables Z_{i} ∈ {0, 1} for every i ∈ V. These variables denote the set of vertices controlled by M. We also define random variables X_{ij} ∈ {0, 1} for every i, j ∈ V. Assume X_{ii} = 1 for every i ∈ V, and X_{ij} = 1 for every (i, j) ∈ E_{1}. Observe that variables X_{ij} for (i, j) ∈ E_{2}\E_{1} are associated to the set of optional edges. Additionally, let Z_{H} be the sum of not necessarily independent random variables Z_{i} ∈ {0, 1} for i ∈ V. Thus, we have the following preliminary result:

Lemma 3. The random variables Z_{i} for all i ∈ V are negatively associated.

Proof: Consider two arbitrary disjoint index sets I, J ⊆ {1, 2, …, n}. Then we want to show that:

E(∑_{i∈I} Z_{i} ∑_{j∈J} Z_{j}) − E(∑_{i∈I} Z_{i})E(∑_{j∈J} Z_{j}) = ∑_{i∈I,j∈J} (E(Z_{i}Z_{j}) − E(Z_{i})E(Z_{j})) ≤ 0

In particular, it is easy to observe (from the definition of the mcsp) that Z_{i} and Z_{j} (for i ≠ j) are independent random variables if they simultaneously belong to M (or U). However, Z_{i} and Z_{j} are negatively associated if they are not in the same set. Generally, for arbitrary index sets I and J, we can establish that P r(Z_{j} = 1 | Z_{i} = 1) ≤ P r(Z_{j} = 1) or, equivalently, P r(Z_{i} = 1 | Z_{j} = 1) ≤ P r(Z_{i} = 1). Thus, for every pair i ∈ I and j ∈ J, we have that E(Z_{i}Z_{j}) = P r(Z_{i}Z_{j} = 1) = P r(Z_{i} = 1)P r(Z_{j} = 1 | Z_{i} = 1) ≤ P r(Z_{i} = 1)P r(Z_{j} = 1) = E(Z_{i})E(Z_{j}), which proves the lemma.

Now, consider our relaxed integer programming formulation. For i, j ∈ V, assume X_{ij} = 1 if i = j or (i, j) ∈ E_{1}. Assume also we assign, as described in Algorithm 2, arbitrarily values X_{ij} for every (i, j) ∈ E_{2}\E_{1}. If Z_{H} is the sum of random variables denoting the value of the randomized solution, it follows from constraints (3)-(6) that:

Z_{H} = ∑_{i∈V} Z_{i} ≤ ∑_{i∈V} min{1; ∑_{j∈M}(a_{ij}/n)X_{ij} − ∑_{j∈V}(a_{ij}/2n)X_{ij} + 1}  (7)

From Lemma 2 and the linearity of expectation one obtains:

E(Z_{H}) = ∑_{i∈V} E(Z_{i}) ≤ ∑_{i∈V} min{1; ∑_{j∈M}(a_{ij}/n)x_{ij}^{∗} − ∑_{j∈V}(a_{ij}/2n)x_{ij}^{∗} + 1},

where E(X_{ij}) = x_{ij}^{∗}. Therefore:

E(Z_{H}) ≤ ∑_{i∈V} min{1; z_{i}^{∗}} ⇒ E(Z_{H}) ≤ ∑_{i∈V} z_{i}^{∗} = y^{∗} for z_{i}^{∗} ∈ [0, 1]  (8)

Recall that Step 1 of Algorithm 2 guarantees a performance ratio equal to \frac{1}{2}. Therefore, each iteration of Algorithm 2 returns a solution with Z_{H} ≥ ẑ/2 (where ẑ denotes the value of the optimal integer solution). Now, as the optimal solution itself may be generated at random, one may concludes, without loss of generality, that E(Z_{H}) is strictly greater than ẑ/2 (otherwise, the solution generated by Algorithm 1 would be optimal). Thus, we assume from (8) that ẑ/2 < E(Z_{H}) ≤ y^{∗}, where E(Z_{H}) = μ = y^{∗}/β for some β ∈ [1, 2).

Now, for some α > 1, to be considered later, define a bad event B ≡ (Z_{H} < y^{∗}/α). Equivalently to the definition of a randomized approximation algorithm (described in the preceding Section), Z_{H} defines an \frac{1}{α}-approximation solution for the mcsp if B^{c} ≠ Ø holds (complementary event).

How small a value for α can we achieve while guaranteeing good events B^{c} ≠ Ø? Since we expect to obtain an approximation algorithm with a superior performance ratio (greater than \frac{1}{2}), it suffices to consider α ∈ (β, k) for some k ∈ (β, 2]. The parameter k will be fixed later. This give us an improved \frac{1}{α}- approximation Z_{H} with nonzero probability. As discussed later, this solution will be made deterministic through derandomization techniques, namely, the method of conditional expectations.

Therefore, a bad event B occurs if Z_{H} < y^{∗}/α. Then:

P r(B) = P r(Z_{H} < \frac{y^{∗}}{α}) = P r(Z_{H} < \frac{βμ}{α}) = P r(Z_{H} < (1 − δ)μ),

where δ = 1 − \frac{β}{α} > 0.

In order to apply the lower CH bound, in addition to the negative association (Lemma 3), all random variables must assume values in the interval (0,1). In our case, however, as observed in Section 3, P r(Z_{i} = 1) = 1 for every i ∈ M_{C} ∪ U_{C} (set of vertices which are always controlled by M) and P r(Z_{i} = 1) = 0 for every i ∈ M_{N} ∪ U_{N} (set of vertices which are never controlled by M). Despite of that, CH bounds may be applied, since the linear programming relaxation is being solved by some interior point method (see Wright [18].)

Therefore, from the lower CH bound and assuming μ > ẑ/2, it follows that:

P r(B) < \frac{1}{exp ((1 − β/α)^{2} \frac{μ}{2})} < \frac{1}{exp ((1 − β/α)^{2} \frac{ẑ}{4})}  (9)

This implies:

P r(B) < \frac{1}{exp((1 − β/α)^{2} \frac{ẑ}{4} − \frac{1}{4})}  (10)

We expect that P r(B) < 1 (probability of bad event). Thus, if we impose this last condition, it follows from (10) that:

P r(B) = \frac{1}{exp((1 − β/α)^{2} \frac{ẑ}{4} − \frac{1}{4})} < 1 for some α ∈ (β, k)  (11)

Additional executions of Step 4 in Algorithm 2 for y > A(k) arbitrarily reduce the failure probability (Monte Carlo method). Therefore, without loss of generality, if P r(B) = C < 1 is the probability of a bad event, and δ > 0 is a given error, ⌈ | log δ/ log C | ⌉ iterations are sufficient to ensure a \frac{1}{α}-approximation algorithm with probability 1 − δ > 0.

Then, we need to determine if there is some value α ∈ (β, k) (where β ≥ 1 and k ≤ 2) for which inequality (11) makes sense. Equivalently, we expect to obtain (ẑ−1)α^{2}−(2ẑβ)α+β^{2}ẑ > 0 for some α ∈ (β, k). By solving the quadratic equation, we obtain the roots:

α′ = \frac{β(ẑ − \sqrt{ẑ})}{ẑ − 1} and α′′ = \frac{β(ẑ + \sqrt{ẑ})}{ẑ − 1}.

Since α > β, it is easy to observe that inequality (ẑ ± \sqrt{ẑ})/(ẑ − 1) > 1 holds only for α′′ with ẑ > 1. In addition, we expect that α′′ < k for some k ∈ (β, 2]. Thus, since β = y^{∗}/μ ≥ 1, it follows that:

α′′ = \frac{y^{∗}(ẑ + \sqrt{ẑ})}{μ(ẑ − 1)} < k ⇒ \frac{y^{∗}(ẑ + \sqrt{ẑ})}{k(ẑ − 1)} < μ ≤ y^{∗}.  (12)

Therefore:

\frac{y^{∗}(ẑ + \sqrt{ẑ})}{k(ẑ − 1)} < y^{∗} ⇒ ẑ + \sqrt{ẑ} < k(ẑ − 1)  (13)

Now, inequality (13) holds only for ẑ > A(k) with:

A(k) = \frac{2k(k − 1) + 1 + \sqrt{4k(k − 1) + 1}}{2(k − 1)^{2}}

Notice that constraint ẑ > 1 above is immediately verified since we have A(k) ≥ 4 for every k ∈ (1, 2]. Finally, from expression (12), since E(Z_{H}) = μ, ẑ ≤ y^{∗} and y^{∗} > A(k), it follows that:

E(Z_{H}) > (\frac{ẑ + \sqrt{ẑ}}{ẑ − 1}) (\frac{y^{∗}}{k} ) > (\frac{y^{∗} + \sqrt{y^{∗}}}{k(y^{∗} − 1)}) ẑ = (\frac{1}{k} + \frac{1 + \sqrt{y^{∗}}}{k(y^{∗} − 1)}) ẑ (14)

Moreover, observe from the above expression that:

\frac{1 + \sqrt{y^{∗}}}{k(y^{∗} − 1)} > 0 and lim_{y^{∗}→∞} \frac{1 + \sqrt{y^{∗}}}{k(y^{∗} − 1)} = 0 for every y^{∗} > A(k).

Thus, inequality (14) gives us a randomized \frac{1}{k} + \frac{1+\sqrt{y^{∗}}}{k(y^{∗}−1)}-approximation algorithm for every y^{∗} > A(k) and k ∈ (β, 2]. Therefore, with high probability and for a large class of instances, this ratio improves the \frac{1}{2}-approximation algorithm in [11]. The case y^{∗} ≤ A(k) may be solved exactly in time O(n^{A(k)}) through the algorithm for the parameterized mcsp in Section 3. Observe for instance that A(k_{1}) > A(k_{2}) for every k_{1}, k_{2} ∈ (β, 2] with k_{1} < k_{2}. In other words, despite the increase in the computational time of the algorithm for the parameterized mcsp, small values of k (for k > β) guarantee improved approximation ratios for every y^{∗} > A(k). Formally, we proved the following result:

Theorem 2. Consider y^{∗} and μ as above. Then, for a given parameter k ∈ (β, 2] with β = y^{∗}/μ, Algorithm 2 defines a randomized \frac{1}{k} + \frac{1+\sqrt{y^{∗}}}{k(y^{∗}−1)}-approximation algorithm for the mcsp.

Unfortunately, we do not know explicitly the value of β = y^{∗}/μ since the expectation μ is unknown and hard to compute. Moreover, we cannot guarantee a parameter k strictly less than 2. This problem is minimized if some good estimations of E(Z_{H}) = μ, and thus of β, are obtained. By running independent experiments with respect to Z_{H}, the recent work of Dagum et al. [2] ensures, for given δ and ϵ, an estimator μ′ of μ within a factor 1 + ϵ and probability at least 1 − δ. Therefore, if this approximation is performed in advance, and if we assume k = min\{2, \frac{y^{∗}}{μ′(1−ϵ)}\}, an improved randomized approximation algorithm (for every instance of the mcsp) may be achieved if k < 2. Notice for instance that, given an interval (β, k), the proof of Theorem 2 guarantees the existence of α ∈ (β, k), thus improving the performance ratio.

6 A derandomized algorithm

Derandomization techniques convert a randomized algorithm into a deterministic one. Here, this is performed through the probabilistic method (introduced by Erdös and Spencer [5]). The main idea is to use the existence proof of some combinatorial structure for actually exhibiting this structure.

The purpose of this section is to derandomize Algorithm 2 by using the method of conditional expectations. In this case, the goal is to convert the expected approximation ratio into a guaranteed approximation ratio while increasing the running time by a factor that is polynomial on the input size. Basically, the method of conditional expectations analyzes the behavior of a randomized approximation algorithm as a computation tree, in a such way that each path from the root to a leaf of this tree corresponds to a possible computation generated by the algorithm.

In order to describe our derandomized procedure for the MCSP, consider inequality (7). Then, it follows that:

Z_{H} = ∑_{i∈V} Z_{i} ≤ ∑_{i∈V} Y_{i}, where Y_{i} = min{1, ∑_{j∈M}(a_{ij}/n)X_{ij}−∑_{j∈V}(a_{ij}/2n)X_{ij}+1}

Recall that X_{ii} = 1 for every i ∈ V, and X_{ij} = 1, ∀(i, j) ∈ E_{1}. In addition, suppose that all optional edges in E_{2}\E_{1} are arbitrarily ordered and indexed by k = 1, …, |E_{2}\E_{1}|. In this section, the notation x_{ij}^{(k)} = 1 has the following meaning: the k-th edge of E_{2}\E_{1}, with endpoints i and j, belongs to the sandwich graph G = (V, E). Otherwise, x_{ij}^{(k)} = 0 means that (i, j) ∉ E. For simplicity, we will suppress indexes i and j and simply write x^{(k)}. Capital letters X^{(k)} mean that a value 0 or 1 was assigned to variable x^{(k)}, for some k ∈ {1, …, |E_{2}\E_{1}|}. Furthermore, the notation E(Z_{H} | x^{(k)} = 0 or 1) denotes the average value produced by the randomized algorithm by computations that set x^{(k)} = 0 or 1.

Thus, from de definition of conditional expectation and from its linearity property one concludes that:

E(Z_{H}) = E(Z_{H} | x^{(1)} = 1)P r(x^{(1)} = 1) + E(Z_{H} | x^{(1)} = 0)P r(x^{(1)} = 0)

≤ max{ ∑_{i∈V} E(Z_{i} | x^{(1)} = 1) ; ∑_{i∈V} E(Z_{i} | x^{(1)} = 0) } = ∑_{i∈V} E(Z_{i} | X^{(1)})

≤ max{∑_{i∈V} E(Z_{i} | X^{(1)}, x^{(2)} = 1) ; ∑_{i∈V} E(Z_{i} | X^{(1)}, x^{(2)} = 0)}

= ∑_{i∈V} E(Z_{i} | X^{(1)}, X^{(2)})

By repeating this process for every edge in E_{2}\E_{1}, one obtains:

E(Z_{H}) ≤ max{∑_{i∈V} E(Z_{i} | X^{(1)}, …, X^{(|E_{2}\E_{1}|)}); ∑_{i∈V} E(Z_{i} | X^{(1)}, …, X^{(|E_{2}\E_{1}|)})}

Therefore, within this framework, a guaranteed performance ratio is polynomially attained through an expected approximation ratio, gathering, in this way, an improved deterministic approximation solution.

Now, from the definition of conditional expectation,

E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0 or 1) = P r(Z_{i} = 1 | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0 or 1),

for every i ∈ V and k = 1, …, |E_{2}\E_{1}|. Unfortunately, for the mcsp, these probabilities are hard to compute. Lemma 4 will give us an alternate way to deal with these expectations without explicitly consider conditional probabilities.

Lemma 4. Suppose that Z_{i} and Y_{i}, for some i ∈ V, are random variables as described above. Then:

(a) E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0) ⇔ E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0)

(b) E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0) ≥ E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ⇔ E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0) ≥ E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1)

Proof: We will prove item (a), the proof of (b) follows analogously. Consider without loss of generality that E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0). Thus, since E(Z_{H}) = y^{∗}/β for some β ∈ [1, 2), it follows from inequalities (7)-(8) and from the definition of conditional expectations that:

E(Z_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0 or 1) = (1/β) E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0 or 1).

Thus:

(1/β)E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ (1/β)E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0).

By multiplying both sides by β, we get the desired inequality

E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0).

The converse is obtained in the same way by first multiplying this last inequality by \frac{1}{β}.

Now, from Lemma 4, it follows that E(Z_{H}) is less than or equal to

max{∑_{i∈V} E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1); ∑_{i∈V} E(Y_{i} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0)},

for k = 1, …, |E_{2}\E_{1}|.

We repeat the process above for every optional edge in E_{2}\E_{1}. Therefore, the sequence X^{(1)}, …, X^{(|E_{2}\E_{1}|)} is obtained deterministically in polynomial time while improving the approximation ratio.

From the preceding section, we have described a randomized algorithm whose expectation E(Z_{H}) is greater than or equal to \frac{1}{k} + \frac{1+\sqrt{y^{∗}}}{k(y^{∗}−1)} for some k ∈ (β, 2] conveniently chosen. Since we expect to obtain a deterministic procedure, it suffices to consider (in the worst case) k = 2 and y^{∗} = θ(n). Observe, from the preceding section, that by setting k = 2 one obtains A(2) = 4. This will give us (for an arbitrary instance) an improved deterministic polynomial time approximation algorithm with performance ratio equal to \frac{1}{2} + \frac{1+\sqrt{n}}{2n−2}.

Algorithm 3: derandomized algorithm for the mcsp

1. compute z_{1} using Algorithm 1

2. solve the linear programming relaxation and return y^{∗}

3. if y^{∗} ≤ 4

then compute z_{H} by executing the algorithm for the parameterized mcsp in Section 3 for parameters A = ⌊y^{∗}⌋, ⌊y^{∗}⌋ − 1, …, 1, 0, until obtaining a Yes answer else for k = 1, …, |E_{2}\E_{1}| do

if E(Y_{k} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 1) ≥ E(Y_{k} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0)

then X^{(k)} ← 1
else X^{(k)} ← 0

compute z_{2} by using the integer feasible function X

z_{H} ← max{z_{1}, z_{2}}

5. return z_{H}

Observe above that expectations E(Y_{k} | X^{(1)}, …, X^{(k−1)}, x^{(k)} = 0 or 1) are easily obtained. This may be accomplished in polynomial time by solving a linear programming problem for every optional edge (settled 0 or 1). If L denotes the length of the input, the linear relaxation has complexity O(n^{3}L) [18], and thus the total complexity of Algorithm 3 will be equal to O(max{n^{4}, |E_{2}\E_{1}|n^{3}L}). Moreover, from Theorem 2, it is straightforward to observe that an improvement of the approximation ratio may be attained if good upper bounds are obtained via the linear relaxation. This may be accomplished, for example, through the use of new reduction rules and/or through the use of additional cutting planes. Notice for instance that, even in the worst case, when y^{∗} = θ(n), one obtains an improved approximation ratio. Formally, we can establish the following result:

Theorem 3. Algorithm 3 guarantees in polynomial time an approximation ratio equal to \frac{1}{2} + \frac{1+\sqrt{n}}{2n−2} for n > 4.

7 Conclusions

We presented an improved deterministic polynomial time approximation algorithm for the Max-Controlled Set Problem through the use of randomized rounding and derandomization techniques. As far as we know, this is the best approximation result for the mcsp. This improves the \frac{1}{2}-approximation procedure presented by Makino, Yamashita and Kameda [11]. A new linear integer programming formulation was presented to define tuned probabilities in our randomized procedure. Through the use of the probabilistic method, we converted a probabilistic proof of existence of an approximated solution into an efficient deterministic algorithm for actually constructing this solution. Additionally, we show that if some good estimations of expectation are obtained in advance, some improved approximation ratios may be attained.

As future work, an interesting question is to decide whether the parameterized mcsp is Fixed Parameter Tractable - FPT. (A problem with parameter A is FPT if it admits an O(f(A)n^{γ}) time algorithm, for some function f and some constant γ independent of A. For details, see [3].) Obtaining non-approximability results for the mcsp and using semidefinite programming relaxation in the randomized rounding procedure are also interesting attempts of research.

Acknowledgments

We thank Marcos Kiwi and Prabhakar Raghavan for their valuable comments and pointers to the literature.

References

1. J.-C. Bermond and D. Peleg, The power of small coalitions in graphs, Proc. 2nd Structural Information and Communication Complexity, Olympia, Carleton University Press, Ottawa, pp. 173–184, 1995.

2. P. Dagum, R. Karp, M. Luby, and S. Ross, An optimal algorithm for Monte Carlo estimation, SIAM Journal on Computing, 29(5) (2000) 1484–1496.

3. R. G. Downey and M. R. Fellows, Fixed parameter tractability and completeness I: Basic results, 21st Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, Canada, 1991.

4. D. Dubashi and D. Ranjan, Balls and bins: A study of negative dependence, Random Structures and Algorithms 13(2) (1998) 99–124.

5. P. Erdös and J. Spencer, “The Probabilistic Method in Combinatorics” , Academic Press, San Diego, 1974.

6. D. Fitoussi and M. Tennenholtz, Minimal social laws, Proc. AAAI’98, pp. 26–31, 1998.

7. M. C. Golumbic, H. Kaplan, and R. Shamir, Graph sandwich problems, Journal of Algorithms, 19 (1994), 449–473.

8. H. Kaplan and R. Shamir, Physical maps and interval sandwich problems: Bounded degrees help, Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems - ISTCS, 1996, pp. 195–201. To appear in Algorithmica under the title “Bounded degree interval sandwich problems”.

9. N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica, 4 (1984), 375–395.

10. N. Linial, D. Peleg, Y. Rabinovich, and N. Saks, Sphere packing and local majorities in graphs, Proc. 2nd Israel Symposium on Theoretical Computer Science, IEEE Computer Society Press, Rockville, MD, pp. 141–149, 1993.

11. K. Makino, M. Yamashita, and T. Kameda, Max-and min-neighborhood monopolies, Algorithmica, 34 (2002), 240–260.

12. R. Motwani and P. Raghavan, “Randomized Algorithms”, Cambridge University Press, London, 1995.

13. D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review, Technical Report CS96-12, Weizmann Institute, Rehovot, 1996.

14. P. Raghavan and C. D. Thompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 7(4) (1987), 365–374.

15. J. D. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in Graph Theory and Computing (R. C. Reed, ed.), Academic Press, New York, 1972, pp. 183–217.

16. Y. Shoham and M. Tennenholtz, Emergent conventions in multi-agent systems: Initial experimental results and observations, Proc. International Conference on Principles of Knowledge Representation and Reasoning, pp. 225–231, 1992.

17. Y. Shoham and M. Tennenholtz, On the systhesis of useful social laws for artificial agent societies, Proc. AAAI’92, pp. 276–281, 1992.

18. S. J. Wright, “Primal-Dual Interior-Point Methods”, SIAM, 1997.

19. M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic and Discrete Methods 2 (1981), 77–79.