Finding cliques and dense subgraphs using edge queries
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916319492833280 |
|---|---|
| author | Csóka, Endre Pongrácz, András |
| author_facet | Csóka, Endre Pongrácz, András |
| contents | We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Recall that the largest clique in $G \sim G(n,1/2)$ has size roughly $2\log_{2} n$. Let $α_{\star}(δ,\ell)$ be the supremum over $α$ such that there exists an algorithm that makes $n^δ$ queries in total to the adjacency matrix of $G$, in a constant $\ell$ number of rounds, and outputs a clique of size $α\log_{2} n$ with high probability. We give improved upper bounds on $α_{\star}(δ,\ell)$ for every $δ\in [1,2)$ and $\ell \geq 3$. We also study analogous questions for finding subgraphs with density at least $η$ for a given $η$, and prove corresponding impossibility results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_06826 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Finding cliques and dense subgraphs using edge queries Csóka, Endre Pongrácz, András Combinatorics Discrete Mathematics 05C80, 05C85, 68Q87, 68W20 We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Recall that the largest clique in $G \sim G(n,1/2)$ has size roughly $2\log_{2} n$. Let $α_{\star}(δ,\ell)$ be the supremum over $α$ such that there exists an algorithm that makes $n^δ$ queries in total to the adjacency matrix of $G$, in a constant $\ell$ number of rounds, and outputs a clique of size $α\log_{2} n$ with high probability. We give improved upper bounds on $α_{\star}(δ,\ell)$ for every $δ\in [1,2)$ and $\ell \geq 3$. We also study analogous questions for finding subgraphs with density at least $η$ for a given $η$, and prove corresponding impossibility results. |
| title | Finding cliques and dense subgraphs using edge queries |
| topic | Combinatorics Discrete Mathematics 05C80, 05C85, 68Q87, 68W20 |
| url | https://arxiv.org/abs/2310.06826 |