Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-03T00:25:17.043Z Has data issue: false hasContentIssue false

An improved derandomized approximation algorithmfor the max-controlled set problem

Published online by Cambridge University Press:  28 February 2011

Carlos Martinhon
Affiliation:
Fluminense Federal University, Institute of Computing, Rua Passo da Pátria 156, Bloco E, 24210-230, Niterói, RJ, Brazil; [email protected]; [email protected]
Fábio Protti
Affiliation:
Fluminense Federal University, Institute of Computing, Rua Passo da Pátria 156, Bloco E, 24210-230, Niterói, RJ, Brazil; [email protected]; [email protected]
Get access

Abstract

A vertex i of a graph G = (V,E) is said to be controlled by $M \subseteq 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\in V$ is controlled by M. Given a set $M \subseteq V$ and two graphs G1 = ($V,E_1$) and G2 = ($V,E_2$) where $E_1\subseteq 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\subseteq E\subseteq 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\leq4$ is solved exactly by considering the parameterized version of the mcsp.) The algorithm is obtained through the use of randomized rounding and derandomization techniques based on the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance.

Type
Research Article
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arora, S. and Safra, S., Probabilistic checking of proofs: A new characterization of NP. J. ACM 45 (1998) 70122. CrossRef
Bermond, J.-C. and Peleg, D., The power of small coalitions in graphs. Discrete Appl. Math. 127 (2003) 399414. CrossRef
Dagum, P., Karp, R., Luby, M. and Ross, S., An optimal algorithm for Monte Carlo estimation. SIAM J. Comput. 29 (2000) 14841496. CrossRef
Downey, R.G. and Fellows, M.R., Fixed parameter tractability and completeness I: Basic results. SIAM J. Comput. 24 (1995) 873921. CrossRef
Dubashi, D. and Ranjan, D., Balls and bins: A study of negative dependence. Random Struct. Algorithms 13 (1998) 99124. 3.0.CO;2-M>CrossRef
P. Erdös and J. Spencer, The Probabilistic Method in Combinatorics. Academic Press, San Diego (1974).
D. Fitoussi and M. Tennenholtz, Minimal social laws. Proc. AAAI'98 (1998) 26–31.
Gandhi, R., Khuler, S., Parthasarathy, S. and Srinivasan, A., Dependent rounding and its applications to approximation algorithms. J. ACM 53 (2006) 324360. CrossRef
Golumbic, M.C., Kaplan, H. and Shamir, R., Graph sandwich problems. J. Algorithms 19 (1994) 449473. CrossRef
Kaplan, H. and Shamir, R., Bounded degree interval sandwich problems. Algorithmica 24 (1999) 96104. CrossRef
Karmarkar, N., A new polynomial time algorithm for linear programming. Combinatorica 4 (1984) 375395. CrossRef
S. Khot, On the power of unique 2-prover 1-round games, in STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, NY, USA, ACM Press (2002) 767–775. CrossRef
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 (1993) 141–149.
Makino, K., Yamashita, M. and Kameda, T., Max-and min-neighborhood monopolies. Algorithmica 34 (2002) 240260. CrossRef
R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, London, 1995.
D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review. Technical Report CS96-12, Weizmann Institute, Rehovot (1996).
Raghavan, P. and Thompson, C.D., Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) 365374. CrossRef
J.D. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in Graph Theory and Computing, edited by R.C. Reed, Academic Press, New York (1972) 183–217.
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 (1992) 225–231.
Y. Shoham and M. Tennenholtz, On the systhesis of useful social laws for artificial agent societies. Proc. AAAI'92 (1992) 276–281.
S.J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997).
Yannakakis, M., Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2 (1981) 7779. CrossRef