×

An improved derandomized approximation algorithm for the max-controlled set problem. (English) Zbl 1218.68196

Summary: 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 is controlled by \(M\). Given a set \(M\subseteq V\) and two graphs \(G_{1}=(V,E_1)\) and \(G_{2} = (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\leq 4\) 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.

MSC:

68W20 Randomized algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP. J. ACM45 (1998) 70-122. Zbl0903.68076 · Zbl 0903.68076 · doi:10.1145/273865.273901
[2] J.-C. Bermond and D. Peleg, The power of small coalitions in graphs. Discrete Appl. Math.127 (2003) 399-414. Zbl1025.68061 · Zbl 1025.68061 · doi:10.1016/S0166-218X(02)00241-X
[3] P. Dagum, R. Karp, M. Luby and S. Ross, An optimal algorithm for Monte Carlo estimation. SIAM J. Comput.29 (2000) 1484-1496. · Zbl 1112.65300 · doi:10.1137/S0097539797315306
[4] R.G. Downey and M.R. Fellows, Fixed parameter tractability and completeness I: Basic results. SIAM J. Comput.24 (1995) 873-921. · Zbl 0830.68063 · doi:10.1137/S0097539792228228
[5] D. Dubashi and D. Ranjan, Balls and bins: A study of negative dependence. Random Struct. Algorithms13 (1998) 99-124. Zbl0964.60503 · Zbl 0964.60503 · doi:10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M
[6] P. Erdös and J. Spencer, The Probabilistic Method in Combinatorics. Academic Press, San Diego (1974). · Zbl 0308.05001
[7] D. Fitoussi and M. Tennenholtz, Minimal social laws. Proc. AAAI’98 (1998) 26-31.
[8] R. Gandhi, S. Khuler, S. Parthasarathy and A. Srinivasan, Dependent rounding and its applications to approximation algorithms. J. ACM53 (2006) 324-360. · Zbl 1312.68233
[9] M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1994) 449-473. · Zbl 0838.68054 · doi:10.1006/jagm.1995.1047
[10] H. Kaplan and R. Shamir, Bounded degree interval sandwich problems. Algorithmica24 (1999) 96-104. Zbl0934.68070 · Zbl 0934.68070 · doi:10.1007/PL00009277
[11] N. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica4 (1984) 375-395. Zbl0684.90062 · Zbl 0684.90062
[12] 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. · Zbl 1192.68367
[13] 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.
[14] K. Makino, M. Yamashita and T. Kameda, Max-and min-neighborhood monopolies. Algorithmica34 (2002) 240-260. · Zbl 1016.68057 · doi:10.1007/s00453-002-0963-8
[15] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, London, 1995. · Zbl 0849.68039
[16] D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review. Technical Report CS96-12, Weizmann Institute, Rehovot (1996).
[17] P. Raghavan and C.D. Thompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica7 (1987) 365-374. · Zbl 0651.90052 · doi:10.1007/BF02579324
[18] 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. Zbl0266.65028 · Zbl 0266.65028
[19] 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.
[20] Y. Shoham and M. Tennenholtz, On the systhesis of useful social laws for artificial agent societies. Proc. AAAI’92 (1992) 276-281.
[21] S.J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997). Zbl0863.65031 · Zbl 0863.65031
[22] M. Yannakakis, Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods2 (1981) 77-79. · Zbl 0496.68033 · doi:10.1137/0602010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.