Large cliques and large independent sets: can they coexist?
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911131837136896 |
|---|---|
| author | Feige, Uriel Pauzner, Ilia |
| author_facet | Feige, Uriel Pauzner, Ilia |
| contents | For a graph $G$ and a parameter $k$, we call a vertex $k$-enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$, and we call it $k$-excluding otherwise. Motivated by issues that arise in secret sharing schemes, we study the complexity of detecting vertices that are $k$-excluding. We show that for every $ε$, for sufficiently large $n$, if $k > (\frac{1}{4} + ε)n$, then every graph on $n$ vertices must have a $k$-excluding vertex, and moreover, such a vertex can be found in polynomial time. In contrast, if $k < (\frac{1}{4} - ε)n$, a regime in which it might be that all vertices are $k$-enabling, deciding whether a graph has no $k$-excluding vertex is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Large cliques and large independent sets: can they coexist? Feige, Uriel Pauzner, Ilia Data Structures and Algorithms Computational Complexity 68R10 F.2.2; G.2.2 For a graph $G$ and a parameter $k$, we call a vertex $k$-enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$, and we call it $k$-excluding otherwise. Motivated by issues that arise in secret sharing schemes, we study the complexity of detecting vertices that are $k$-excluding. We show that for every $ε$, for sufficiently large $n$, if $k > (\frac{1}{4} + ε)n$, then every graph on $n$ vertices must have a $k$-excluding vertex, and moreover, such a vertex can be found in polynomial time. In contrast, if $k < (\frac{1}{4} - ε)n$, a regime in which it might be that all vertices are $k$-enabling, deciding whether a graph has no $k$-excluding vertex is NP-hard. |
| title | Large cliques and large independent sets: can they coexist? |
| topic | Data Structures and Algorithms Computational Complexity 68R10 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2509.00721 |