On the problem of finding approximation of bipatite cliques
https://doi.org/10.15514/ISPRAS-2017-29(3)-12
Abstract
In this paper, we consider the problem of finding large hidden clique in random graph and it’s analog for bipartite graphs.
References
1. S. Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, Proceedings of the 42th Annual Symposium on Foundations of Computer Science, 2001, pp. 600-609
2. U. Feige. Relations between average case complexity and approximation complexity, Proceedings of the 34th Annual Symposium on the Theory of Computing, 2002, pp. 534-543.
3. R. Peters. The maximum edge biclique problem is NP-complete, Research Memorandum 789, Faculty of Economics and Business Administration, Tilburg University, 2000.
4. U. Feige, R. Krauthhgamer. Finding and sertifying a large hidden clique in a semi-random graph, Random Structures and Algorithms, v. 13, 1998, pp. 457-466.
5. A. Juels, M. Peinado. Hiding Cliques for Cryptographic Security, Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 678-684.
6. R. Karp. Reducibility among combinatorial problems, in The complexity of computer computations, Plenum Press, New York, 1972, pp. 85-103.
7. R. Karp. The probabilistic analysis of some combinatorial search algorithms, in Algorithms and Complexity: New directions and recent results, Academic Press, 1976, pp. 1-19.
8. L. Kucera. Expected complexity of graph partitioning problems, Discrete Applied Mathematics, v. 57, 1995„ pp. 193-212.
9. M. Jerrum. Large cliques elude the Metropolis process, Random Structures and Algorithms, v. 3, 1992, pp. 347-359.
10. J. Hastad. Clique is hard to approximate within , Proceedings of the 37th Annual IEEE Symposium on Foundations of Computing, 1997, pp. 627-636.
11. U. Feige, S. Kogan. Hardness of approximation of the balanced complete bipartite subgraph problem.
12. N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, N. Xie. Testing k-wise and almost k-wise independence, Proc. Annual Symposium on the Theory of Computing, 2007, pp. 496-505.
13. N. Alon, M. Krivelevich, B. Sudakov. Finding a large hidden clique in a random graph, Random Structures and Algorithms, 1998, v. 13, pp. 457-466.
Review
For citations:
Kuzyurin N.N. On the problem of finding approximation of bipatite cliques. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(3):225-232. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(3)-12
Email this article 