Finding Dense Subgraphs in G(n,1/2)
| dc.creator | Sarma, Atish Das | |
| dc.creator | Deshpande, Amit | |
| dc.creator | Kannan, Ravi | |
| dc.date | 2008-07-31 | |
| dc.date | 2008-09-22 | |
| dc.date.accessioned | 2026-07-07T10:03:56Z | |
| dc.date.available | 2026-07-07T10:03:56Z | |
| dc.description | Finding the largest clique is a notoriously hard problem, even on random graphs. It is known that the clique number of a random graph G(n,1/2) is almost surely either k or k+1, where k = 2log n - 2log(log n) - 1. However, a simple greedy algorithm finds a clique of size only (1+o(1))log n, with high probability, and finding larger cliques -- that of size even (1+ epsilon)log n -- in randomized polynomial time has been a long-standing open problem. In this paper, we study the following generalization: given a random graph G(n,1/2), find the largest subgraph with edge density at least (1-delta). We show that a simple modification of the greedy algorithm finds a subset of 2log n vertices whose induced subgraph has edge density at least 0.951, with high probability. To complement this, we show that almost surely there is no subset of 2.784log n vertices whose induced subgraph has edge density 0.951 or more. | |
| dc.description | 6 pages | |
| dc.identifier | https://arxiv.org/abs/0807.5111 | |
| dc.identifier | http://arxiv.org/abs/0807.5111 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169481 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Finding Dense Subgraphs in G(n,1/2) | |
| dc.type | text |